QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#695074 | #6746. Merge the Rectangles | fgz# | TL | 84ms | 21608kb | C++23 | 2.5kb | 2024-10-31 19:16:36 | 2024-10-31 19:16:36 |
Judging History
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 <= 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';
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3504kb
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: 38ms
memory: 21156kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 84ms
memory: 21608kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 35ms
memory: 21260kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 38ms
memory: 21424kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...