QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386977 | #6746. Merge the Rectangles | k1nsom | WA | 15ms | 117560kb | C++17 | 3.2kb | 2024-04-11 22:12:06 | 2024-04-11 22:12:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 300005
#define ednl '\n'
#define int long long
int n, m, maxn = 0, a[1510][1510] = {0}, b[1510][1510] = {0}, cnt[1510][1510] = {0};
bool vis[1510][1510] = {0};
struct ra
{
int space, sx, sy, tx, ty;
} tmp;
vector<ra> v[N], s1[1510][1510], s2[1510][1510];
signed main()
{
cin >> n >> m;
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
{
char c;
cin >> c;
a[i][j] = c - '0';
}
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++)
{
char c;
cin >> c;
b[i][j] = c - '0';
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!vis[i][j])
{
vis[i][j] = 1;
int sx = i, sy = j, tx = i, ty = j;
while (tx <= n && !a[tx][j])
{
tx++;
if (tx > n)
{
tx--;
break;
}
}
while (ty <= m && !b[i][ty])
{
ty++;
if (ty > m)
{
ty--;
break;
}
}
ra tmp = {(ty - sy + 1) * (tx - sx + 1), sx, sy, tx, ty};
for (int t = i; t <= tx; t++)
for (int k = j; k <= ty; k++)
vis[t][k] = 1;
if (!s1[tmp.sx][tmp.tx].empty())
{
ra u = s1[tmp.sx][tmp.tx][0];
s1[tmp.sx][tmp.tx].pop_back();
ra tmp2;
tmp2.sx = min(u.sx, tmp.sx);
tmp2.sy = min(tmp.sy, u.sy);
tmp2.tx = max(u.tx, tmp.tx);
tmp2.ty = max(u.ty, tmp.ty);
tmp2.space = (tmp2.ty - tmp2.sy + 1) * (tmp2.tx - tmp2.sx + 1);
s1[tmp2.sx][tmp2.tx].push_back(tmp2);
s2[tmp2.sy][tmp2.ty].push_back(tmp2);
s2[u.sy][u.ty].pop_back();
}
else if (!s2[tmp.sy][tmp.ty].empty())
{
ra u = s2[tmp.sy][tmp.ty][0];
s2[tmp.sy][tmp.ty].pop_back();
ra tmp2;
tmp2.sx = min(u.sx, tmp.sx);
tmp2.sy = min(tmp.sy, u.sy);
tmp2.tx = max(u.tx, tmp.tx);
tmp2.ty = max(u.ty, tmp.ty);
tmp2.space = (tmp2.ty - tmp2.sy + 1) * (tmp2.tx - tmp2.sx + 1);
s1[tmp2.sx][tmp2.tx].push_back(tmp2);
s2[tmp2.sy][tmp2.ty].push_back(tmp2);
s1[u.sx][u.tx].pop_back();
}
else
{
s2[tmp.sy][tmp.ty].push_back(tmp);
s1[tmp.sx][tmp.tx].push_back(tmp);
}
maxn = max(tmp.space, maxn);
}
if (!s1[n][m].empty())
cout << "YES";
else
cout << "NO";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 15ms
memory: 117560kb
input:
3 4 0000 0111 101 101 110
output:
NO
result:
wrong answer expected YES, found NO