QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#521833 | #7051. Largest Common Submatrix | Symmetree | WA | 0ms | 12088kb | C++14 | 2.4kb | 2024-08-16 15:34:10 | 2024-08-16 15:34:11 |
Judging History
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'