QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#370789 | #6746. Merge the Rectangles | Lysus | WA | 21ms | 31792kb | C++20 | 1.7kb | 2024-03-29 16:36:52 | 2024-03-29 16:36:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2010;
int n, m, sum[2][N][N];
string a[N], b[N];
void solve() {
cin >> n >> m;
int Idx = 0, cnt = 0;
for(int i = 1; i < n; ++i) {
cin >> a[i];
a[i] = " " + a[i];
}
for(int i = 1; i < n; ++i) {
for(int j = 1; j <= m; ++j) {
sum[0][i][j] = sum[0][i][j - 1] + (a[i][j] == '1');
}
}
for(int i = 1; i <= n; ++i) {
cin >> b[i];
b[i] = " " + b[i];
}
for(int j = 1; j < m; ++j) {
for(int i = 1; i <= n; ++i) {
sum[1][i][j] = sum[1][i - 1][j] + (b[i][j] == '1');
}
}
auto work = [&](auto self, int x1, int y1, int x2, int y2) -> int {
int flag = 1, cnt = 0, mark = 0;
if(x1 >= x2 || y1 >= y2) return 1;
if(x1 < 1 || x2 > n || y1 < 1 || y2 > m) return 1;
for(int i = x1; i < x2; ++i) {
cnt += sum[0][i][y2] - sum[0][i][y1 - 1];
if(sum[0][i][y2] - sum[0][i][y1 - 1] == y2 - y1 + 1) {
mark = 1;
flag &= self(self, x1, y1, i - 1, y2);
flag &= self(self, i + 1, y1, x2, y2);
break;
}
}
for(int j = y1; j < y2; ++j) {
cnt += sum[1][x2][j] - sum[1][x1][j - 1];
if(sum[1][x2][j] - sum[1][x1][j - 1] == x2 - x1 + 1) {
mark = 1;
flag &= self(self, x1, y1, x2, j - 1);
flag &= self(self, x1, j + 1, x2, y2);
break;
}
}
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << mark << " " << cnt << '\n';
if(!mark && cnt) return 0;
else return flag;
};
int flag = work(work, 1, 1, n, m);
if(flag) cout << "YES\n";
else cout << "NO\n";
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
/*
3 3
111
111
11
11
11
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3768kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 19ms
memory: 31464kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 11ms
memory: 31792kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 11ms
memory: 31616kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: -100
Wrong Answer
time: 21ms
memory: 31564kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
NO
result:
wrong answer expected YES, found NO