QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#360972 | #6746. Merge the Rectangles | sacave | TL | 12ms | 25584kb | C++14 | 2.5kb | 2024-03-22 17:01:29 | 2024-03-22 17:01:29 |
Judging History
answer
#include<bits/stdc++.h>
#define endl "\n"
#define x first
#define y second
#define no cout << "No" << endl
#define yes cout << "Yes" << endl
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1510;
const int inf = 0x3f3f3f3f;
const ll lnf = 1e18;
int T,n,m;
int dx[4] = {0,1,-1,0},dy[4] = {1,0,0,-1};
string a[N],b[N];
int hen[N][N],shu[N][N];
bool flag = 1;
map<pair<PII,PII>,int> mp;
void dfs(int x1,int y1,int x2,int y2){
if(mp.count({{x1,y1},{x2,y2}})) return ;
mp[{{x1,y1},{x2,y2}}] = 1;
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
if(x1 == x2 || y1 == y2) return ;
bool t = 0;
for(int i=x1;i<=x2;i++){
// cout << hen[i][y2] - hen[i][y1] << endl;
if(hen[i][y2] - hen[i][y1] == y2 - y1){
// cout << "YES" << endl;
dfs(x1,y1,i,y2);
dfs(i,y1,x2,y2);
// return ;
t = 1;
}
}
for(int i=y1;i<=y2;i++){
if(shu[x2][i] - shu[x1][i] == x2 - x1){
dfs(x1,y1,x2,i);
dfs(x1,i,x2,y2);
// return ;
t = 1;
// return ;
}
}
if(t) return ;
for(int i=x1;i<=x2;i++){
int d = hen[i][y2] - hen[i][y1];
if(d >= 1 && d != y2 - y1) flag = 0;
// if(!flag){
// cout << "row : " << i << endl;
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
// exit(0);
// }
}
for(int i=y1;i<=y2;i++){
int d = shu[x2][i] - shu[x1][i];
if(d >= 1 && d != x2 - x1) flag = 0;
// if(!flag){
// cout << "col : " << i << endl;
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
// exit(0);
// }
}
}
void solve(){
cin >> n >> m;
for(int i=1;i<n;i++) cin >> a[i] ,a[i] = 'a' + a[i];
for(int i=1;i<=n;i++) {
cin >> b[i];
b[i] = '1' + b[i];
}
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
hen[i][j] = a[i][j] - '0';
hen[i][j] += hen[i][j-1];
}
}
for(int j=1;j<m;j++){
for(int i=1;i<=n;i++){
shu[i][j] = b[i][j] - '0';
shu[i][j] += shu[i-1][j];
}
}
// for(int i=1;i<=n;i++) hen[i][m] += hen[i][m-1];
// for(int i=1;i<=m;i++) shu[n][i] += shu[n-1][i];
// for(int i=0;i<=n;i++){
// for(int j=0;j<=m;j++){
// cout << hen[i][j] << ' ';
// }
// cout << endl;
// }
// cout << endl;
// for(int i=0;i<=n;i++){
// for(int j=0;j<=m;j++){
// cout << shu[i][j] << ' ';
// }
// cout << endl;
// }
// cout << endl;
dfs(0,0,n,m);
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3760kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 12ms
memory: 25584kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...