QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521833#7051. Largest Common SubmatrixSymmetreeWA 0ms12088kbC++142.4kb2024-08-16 15:34:102024-08-16 15:34:11

Judging History

你现在查看的是最新测评结果

  • [2024-08-16 15:34:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:12088kb
  • [2024-08-16 15:34:10]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<functional>
#include<utility>
#include<cassert>
using namespace std;
inline int read(){
	int x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}
const int N = 1011;
int n,m,a[N][N],b[N][N],pos[N * N],lx[N][N],ly[N][N], s[N], tt;
#define p(x,y) (x - 1) * (m) + (y)
vector<int> st[N];
int main(){
	int i,j;
	n = read(),m = read();
	for(i = 1;i <= n;i++){
		for(j = 1;j <= m;j++){
			a[i][j] = read();
			pos[a[i][j]] = p(i,j);
		}
	}
	for(i = 1;i <= n;i++){
		for(j = 1;j <= m;j++){
			b[i][j] = read();
			//y = pos[b[i][j]] % m,x = (pos[b[i][j]] - y) / m + 1;
			b[i][j] = pos[b[i][j]] - j - (i - 1) * m;
		}
	}
	for(i = 1;i <= n;i++){
		lx[i][m] = m;
		for(j = m - 1;j >= 1;j--){
			if(b[i][j] == b[i][j + 1]) lx[i][j] = lx[i][j + 1];
			else lx[i][j] = j;
			//printf("%d? ",lx[i][j]);
		}
		//puts("");
	}
	for(j = 1;j <= m;j++){
		ly[n][j] = n; st[j].push_back(n + 1);
		for(i = n - 1;i >= 1;i--){
			if(b[i][j] == b[i + 1][j]) ly[i][j] = ly[i + 1][j];
			else ly[i][j] = i, st[j].push_back(i + 1);
			//printf("%d! ",ly[i][j]);
		}
		if(st[j].back() != 1) st[j].push_back(1);
		reverse(st[j].begin(), st[j].end());
//		puts("");
//		printf("%d: ", j);
//		for(int x: st[j]) printf("%d ", x); puts("");
	}
//	for(int j = m; j; --j) {
//		for(int i = 1; i <= n; ++i) printf("%d ", b[i][j]);
//		puts("");
//	} puts("");
//	for(int j = m; j; --j) {
//		for(int i = 1; i <= n; ++i) printf("%d ", lx[i][j]);
//		puts("");
//	} puts("");
//	for(int j = m; j; --j) {
//		for(int i = 1; i <= n; ++i) printf("%d ", ly[i][j]);
//		puts("");
//	} puts("");
	int res = 0;
	for(int j = 1; j <= m; ++j) {
		for(int i = 0; i < (int)st[j].size() - 1; ++i) {
			tt = 0;
			for(int x = st[j][i]; x < st[j][i + 1]; ++x) {
				while(tt && lx[s[tt]][j] >= lx[x][j]) --tt;
				if(tt) res = max(res, (x - s[tt]) * (lx[x][j] - j + 1));
				else res = max(res, lx[x][j] - j + 1);
				s[++tt] = x;
			}
		}
	}
	printf("%d\n",res);
	return 0;
}
/*
3 4
5 6 7 8
1 2 3 4
9 10 11 12
5 6 8 7
1 2 4 3
12 11 10 9
*/
/*
3 4
1 2 4 5
3 6 12 11
8 9 7 10
10 7 9 8
11 12 6 3
4 5 2 1
*/

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 12088kb

input:

3 4
5 6 7 8
1 2 3 4
9 10 11 12
5 6 8 7
1 2 4 3
12 11 10 9

output:

2

result:

wrong answer 1st numbers differ - expected: '4', found: '2'