QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#522042	#7051. Largest Common Submatrix	qqbb	WA	13ms	14216kb	C++20	4.1kb	2024-08-16 17:47:15	2024-08-16 17:47:20

Judging History

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

[2024-08-16 17:47:20]
评测

测评结果：WA
用时：13ms
内存：14216kb

查看

[2024-08-16 17:47:15]
提交

answer

#include <bits/stdc++.h>
#define qqbb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define endl '\n'
#define _ <<' '<<
#define lb(x) x & -x
#define AA cerr<<"AA"<<endl;
using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;

const int N = 2e5 + 10, M = 4e5 + 10;

int vis[1010][1010];
int ma[1010][1010];
int mb[1010][1010];
int n,m;
map<int,pii> mpa;
map<int,pii> mpb;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

int cnt = 0;
int le[1010],ri[1010];
int lo[1010],hi[1010];
int h[1010][1010],l[1010][1010],r[1010][1010];

bool check(int x, int y,int detx,int dety){
    if(vis[x][y] || x<1 || x>n || y<1 || y>m) return false;
    if(detx<1 || detx>n || dety<1 || dety>m) return false;
    if(ma[x][y] != mb[detx][dety]) return false;
    return true;
}
void bfs(int sx,int sy){
    queue<pii> q;
    q.push({sx,sy});
    while (!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        le[cnt] = min(le[cnt],y);
        ri[cnt] = max(ri[cnt],y);
        lo[cnt] = min(lo[cnt],x);
        hi[cnt] = max(hi[cnt],x);
        q.pop();
        vis[x][y] = cnt;
        for (int i = 0; i < 4; i++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            int detx = mpb[ma[x][y]].first + dir[i][0];
            int dety = mpb[ma[x][y]].second + dir[i][1];
            if (check(nx,ny,detx,dety)){
                q.push({nx,ny});   
            }
        }
    }
}


void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ma[i][j];
            mpa[ma[i][j]] = {i,j};
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mb[i][j];
            mpb[mb[i][j]] = {i,j};
        }
    }
    for(int i=1;i<=1009;i++){
        le[i] = inf;
        lo[i] = inf;
        ri[i] = -1;
        hi[i] = -1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(vis[i][j] == 0){
                cnt++;
                bfs(i,j);
            }
        }
    }
    // for(int i=1;i<=cnt;i++){
    //     int ans = 0;
    //     for(int res=1;res<=ri[i]-le[i]+1;res++){
    //         for(int loo = lo[i];loo<=hi[i];loo++){
    //             for(int x = le[i];x<=le[i] + res -1;x++){
    //                 if(vis[loo][x]){

    //                 }
    //             }
    //         }   
    //     }
    // }
    int res = -inf;
    for (int tgt = 1;tgt<=cnt;tgt++){
        // cout<<lo[tgt] _ hi[tgt] _ 1 _ m<<endl;

        int ans = 0;
        for(int i=lo[tgt];i<=hi[tgt];i++){
            for(int j=1;j<=m;j++){
                h[i][j] = 1;
                r[i][j] = l[i][j] = j;
            }
            for(int j=1+1;j<=m;j++)
                if (vis[i][j] == tgt && vis[i][j-1] == tgt)
                    l[i][j] = l[i][j-1];
            for(int j=m-1;j>1-1;j--){
                if (vis[i][j] == tgt && vis[i][j+1] == tgt)
                    r[i][j] = r[i][j+1];
            }
        }
        for(int i=lo[tgt];i<=hi[tgt];i++){
            for(int j=1;j<=m;j++){
                if (i>lo[tgt] && vis[i][j] == tgt){
                    if (vis[i-1][j] == tgt){
                        h[i][j] = h[i-1][j]+1;
                        if (l[i-1][j] > l[i][j])
                            l[i][j] = l[i-1][j];
                        if (r[i-1][j] < r[i][j])
                            r[i][j] = r[i-1][j];
                    }
                    if ((r[i][j]-l[i][j]+1)*h[i][j]>ans)
                        ans = (r[i][j]-l[i][j]+1) * h[i][j];
                }
            }
        }
        res = max(res,ans);
    }
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<vis[i][j]<<' ';
    //     }
    //     cout<<endl;
    // }
    cout<<res;
}

signed main(){
    qqbb;
//	cout<<fixed<<setprecision(0);
    int Test=1;
//	cin>>Test;
    while(Test--){
        solve();
    }
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 11808kb

input:

output:

result:

ok 1 number(s): "4"

Test #2:

score: 0

Accepted

time: 13ms

memory: 12548kb

input:

10 10
13 2 57 50 1 28 37 87 30 46
66 47 33 69 83 52 97 55 91 18
9 48 23 35 98 8 7 95 90 5
3 53 43 36 96 59 26 4 70 17
71 100 15 94 25 72 84 89 21 73
64 34 22 29 42 92 85 78 86 62
99 79 67 11 6 19 24 51 77 74
75 16 88 44 93 39 41 82 56 65
12 40 63 54 10 60 32 45 20 80
49 61 76 14 81 68 27 31 58 38
13...

output:

result:

ok 1 number(s): "100"

Test #3:

score: 0

Accepted

time: 10ms

memory: 12476kb

input:

10 10
6 48 98 83 7 56 22 49 61 34
8 87 91 100 16 17 86 24 9 23
94 50 81 59 51 21 52 20 33 25
73 1 70 45 36 31 88 90 12 69
64 57 60 5 85 29 37 96 92 41
89 67 79 84 35 68 46 18 38 63
27 55 65 95 11 43 47 72 80 66
75 39 58 62 77 53 15 40 3 71
32 82 10 99 44 2 30 76 74 28
19 78 13 97 26 42 54 14 4 93
6 ...

output:

result:

ok 1 number(s): "80"

Test #4:

score: 0

Accepted

time: 8ms

memory: 12408kb

input:

10 10
37 16 29 24 14 20 41 63 4 15
71 99 17 26 33 47 83 55 89 52
32 22 95 44 81 93 78 31 42 12
94 70 25 46 18 97 57 62 68 67
21 69 54 27 13 96 64 48 59 28
11 49 9 73 100 90 85 36 2 58
74 53 98 34 7 5 3 91 23 76
77 86 84 92 50 51 45 61 30 66
35 1 10 79 39 6 80 82 43 88
75 60 38 87 40 8 19 56 72 65
37...

output:

result:

ok 1 number(s): "80"

Test #5:

score: 0

Accepted

time: 2ms

memory: 11872kb

input:

10 10
22 71 28 19 15 47 31 88 95 85
56 79 87 43 96 39 45 97 83 36
6 21 98 34 65 91 58 62 41 42
26 37 74 8 27 55 84 75 20 35
49 24 51 32 50 68 52 5 10 11
25 73 38 92 63 67 64 13 46 78
57 53 23 54 16 99 17 40 82 30
61 81 48 7 86 4 3 60 93 76
90 18 29 44 1 100 2 69 9 12
80 70 33 94 66 72 77 14 59 89
22...

output:

result:

ok 1 number(s): "24"

Test #6:

score: 0

Accepted

time: 0ms

memory: 11972kb

input:

10 10
35 58 83 13 75 51 32 97 76 6
63 96 52 77 65 59 90 86 68 9
22 16 56 74 100 91 44 66 8 79
28 21 17 94 31 60 25 24 64 14
55 71 81 67 53 7 95 41 30 40
78 54 48 10 34 47 3 70 98 38
61 89 42 49 50 20 45 18 62 27
73 15 37 84 57 33 88 2 82 72
85 29 80 26 43 39 92 1 93 19
99 11 5 69 87 12 46 4 23 36
97...

output:

result:

ok 1 number(s): "24"

Test #7:

score: 0

Accepted

time: 0ms

memory: 14216kb

input:

10 10
15 53 47 95 2 80 94 98 17 99
34 37 89 59 49 41 25 29 79 84
45 42 19 20 70 40 4 73 58 76
51 81 87 65 3 10 1 93 27 38
39 96 13 63 8 30 35 68 52 5
75 83 18 88 9 100 92 14 22 46
32 72 69 6 11 12 90 86 62 48
82 61 60 74 71 44 43 16 23 57
26 21 91 64 77 33 55 24 54 78
28 7 36 85 50 31 56 67 97 66
45...

output:

result:

ok 1 number(s): "60"

Test #8:

score: -100

Wrong Answer

time: 2ms

memory: 11860kb

input:

10 10
11 17 94 61 73 42 79 40 2 7
35 96 24 100 85 46 22 9 98 97
51 44 27 14 48 21 33 36 45 34
56 4 39 6 63 75 74 54 57 66
59 37 10 93 58 78 89 72 55 30
64 32 68 83 38 90 99 67 69 95
49 41 91 71 5 19 26 47 80 52
84 70 13 20 77 12 8 86 88 82
16 43 50 25 53 1 29 81 76 92
28 18 31 87 3 15 65 60 62 23
11...

output:

result:

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