QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694886 | #6746. Merge the Rectangles | R73757565# | TL | 85ms | 21580kb | C++23 | 2.4kb | 2024-10-31 18:53:06 | 2024-10-31 18:53:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
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;
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;
}
}
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" << endl;
}else cout << "NO" << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 30ms
memory: 21096kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 85ms
memory: 21580kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 34ms
memory: 21332kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 43ms
memory: 21332kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...