QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#406135 | #6746. Merge the Rectangles | ROCKET | TL | 37ms | 25412kb | C++17 | 2.5kb | 2024-05-06 20:55:59 | 2024-05-06 20:56:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
#define pb push_back
// #define int ll
#define pp pop_back
#define lowbit(x) ((x) & (-x))
typedef double db ;
typedef pair<int,int> pii;
const int N = 1e6+7, M = 207, inf = 0x3f3f3f3f, mod = 1e9 + 7;
int n, m;
string s[1507];
vector<vector<char>> a, b;
int s1[1507][1507], s2[1507][1507];
bool dfs(int x1, int y1, int x2, int y2) {
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
int f1 = 1, f = 1, f0 = 1;
for(int i = x1; i < x2; i++) {
// int ok1 = 0, ok2 = 0;
// for(int j = y1; j <= y2; j++) {
// if(a[i][j] == 1) ok1 = true;
// else ok2 = true;
// }
if(s1[i][y2] - s1[i][y1 - 1] == y2 - y1 + 1) {
f = f & dfs(x1, y1, i, y2);
f = f & dfs(i + 1, y1, x2, y2);
f0 = false;
break;
}
if(s1[i][y2] - s1[i][y1 - 1] != 0) {
f1 = false;
}
}
if(f0 == 0) return f;
for(int i = y1; i < y2; i++) {
// int ok1 = 0, ok2 = 0;
// for(int j = x1; j <= x2; j++) {
// if(b[j][i] == 1) ok1 = true;
// else ok2 = true;
// }
if(s2[x2][i] - s2[x1 - 1][i] == x2 - x1 + 1) {
f = f & dfs(x1, y1, y1, i);
f = f & dfs(x1, i + 1, x2, y2);
// cout << f << endl;
f0 = false;
break;
}
if(s2[x2][i] - s2[x1 - 1][i] != 0) {
f1 = false;
}
}
if(f0 == 0) return f;
return (f & f1);
}
void solve()
{
cin >> n >> m;
a = vector<vector<char>>(n + 7, vector<char>(m + 7));
b = vector<vector<char>>(n + 7, vector<char>(m + 7));
for(int i = 1; i < n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
s1[i][j] = s1[i][j - 1] + a[i][j] - '0';
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m - 1; j++) {
cin >> b[i][j];
s2[i][j] = s2[i - 1][j] + b[i][j] - '0';
}
}
bool f = dfs(1, 1, n, m);
if(f) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int tt = 1;
// cin >> tt;
while(tt--){
solve();
}
// cout << fixed << setprecision(10) << c << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5628kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 5876kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 37ms
memory: 25412kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...