QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#695042#6746. Merge the Rectanglesfgz#TL 81ms21848kbC++232.5kb2024-10-31 19:13:032024-10-31 19:13:05

Judging History

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

  • [2024-10-31 19:13:05]
  • 评测
  • 测评结果:TL
  • 用时:81ms
  • 内存:21848kb
  • [2024-10-31 19:13:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
 
signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    // n = 1500, m = 1500;

    vector<vector<int>> ex(n + 10, vector<int>(m + 10));
    vector<vector<int>> ey(n + 10, vector<int>(m + 10));
    
    for(int i = 1; i <= n - 1; i ++){
        for(int j = 1; j <= m; j ++){
            char c;
            cin >> c;
            ex[i][j] = (c == '1');
            ex[i][j] += ex[i - 1][j] + ex[i][j - 1] - ex[i - 1][j - 1]; 
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m - 1; j ++){
            char c;
            cin >> c;
            ey[i][j] = (c == '1');
            ey[i][j] += ey[i - 1][j] + ey[i][j - 1] - ey[i - 1][j - 1]; 
        }
    }

    auto checkx =[&](int x, int y1, int y2){
        if(y1 == y2)return true;
        int tot = ex[x][y2] - ex[x][y1] - ex[x - 1][y2] + ex[x - 1][y1];
        if(tot == abs(y1 - y2))return true;
        else return false;
    };
    auto checky =[&](int y, int x1, int x2){
        if(x1 == x2)return true;
        int tot = ey[x2][y] - ey[x1][y] - ey[x2][y - 1] + ey[x1][y - 1];
        if(tot == abs(x1 - x2))return true;
        else return false; 
    };

    // for(int i = 1; i < n; i ++){
    //     for(int j = 1; j <= m; j ++)
    //         cout << ex[i][j] << " ";
    //     cout << endl;
    // }
    // for(int i = 1; i <= n; i ++){
    //     for(int j = 1; j < m; j ++)
    //         cout << ey[i][j] << " ";
    //     cout << endl;
    // }

    function< bool(int, int, int, int)> dfs =[&] (int x1, int y1, int x2, int y2){
        // 
        if(x1 + 1 >= x2 && y1 + 1 >= y2)return true;
        int tx = ex[x2 - 1][y2] - ex[x1][y2] - ex[x2 - 1][y1] + ex[x1][y1];
        int ty = ey[x2][y2 - 1] - ey[x1][y2 - 1] - ey[x2][y1] + ey[x1][y1];
        if(tx == ty && tx == 0)return true;

        if (tx){
            for(int i = x1 + 1; i <= x2 - 1; i ++){ // 
                // y1, y2 
                if(checkx(i, y1, y2)){
                    if(dfs(x1, y1, i, y2) && dfs(i, y1, x2, y2))return true;
                }
            }
        }

        if (ty) {
            for(int i = y1 + 1; i <= y2 - 1; i ++){
                // x1, x2
                if(checky(i, x1, x2)){
                    if(dfs(x1, y1, x2, i) && dfs(x1, i, x2, y2))return true;
                }
            }
        }
        return false;
    };

    if(dfs(0, 0, n, m)){
        cout << "YES" << '\n';
    }else cout << "NO" << '\n';

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 34ms
memory: 21096kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 81ms
memory: 21848kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 31ms
memory: 21296kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 34ms
memory: 21404kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #7:

score: -100
Time Limit Exceeded

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:


result: