QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661709 | #6746. Merge the Rectangles | ucup-team1769# | TL | 0ms | 3544kb | C++20 | 10.0kb | 2024-10-20 17:43:06 | 2024-10-20 17:43:09 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <map>
#include <cstring>
using namespace std;
using i64 = long long;
const int INF = 1e9 + 7;
const i64 mod = 998244353;
int n, m;
int vec[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void solve()
{
cin >> n >> m;
vector<string> a(n);
vector<string> b(n);
for (int i = 0; i < n - 1; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
vector<vector<int>> box(n + 3, vector<int>(m + 3, 0));
// vector<vector<bool>> vis(n + 3, vector<bool>(n + 3));
auto bfs = [&](int x, int y, int f) -> void
{
queue<pair<int, int>> q;
q.push({x, y});
while (!q.empty())
{
auto [ux, uy] = q.front();
box[ux][uy] = f;
q.pop();
for (auto [dx, dy] : vec)
{
int nx = ux + dx, ny = uy + dy;
if (nx < 1 || nx > n || ny < 1 || ny > m)
continue;
if (box[nx][ny])
continue;
// down
if (nx > ux && a[ux - 1][ny - 1] == '1')
continue;
// up
if (nx < ux && ux - 2 >= 0 && a[ux - 2][uy - 1] == '1')
continue;
// right
if (ny > uy && b[ux - 1][uy - 1] == '1')
continue;
// left
if (ny < uy && b[ux - 1][uy - 2] == '1')
continue;
q.push({nx, ny});
}
}
};
int cnt = 0;
vector<pair<int, int>> all;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (box[i][j])
continue;
bfs(i, j, ++cnt);
all.emplace_back(i, j);
}
}
//
vector<vector<pair<int, int>>> vc1(n + 3, vector<pair<int, int>>(m + 3, {-1, -1}));
vector<vector<pair<int, int>>> vc2(n + 3, vector<pair<int, int>>(m + 3, {-1, -1}));
auto check = [&](int x, int y, int opt) -> bool
{
if (opt)
return !(vc1[x][y].first == -1 && vc1[x][y].second == -1);
else
return !(vc2[x][y].first == -1 && vc2[x][y].second == -1);
};
// map<pair<int, int>, pair<int, int>> mp1; // 左上角
// map<pair<int, int>, pair<int, int>> mp2; // 右下角
queue<array<int, 4>> q;
for (int i = 1; i <= cnt; i++)
{
auto [x, y] = all[i - 1];
int x1 = x, y1 = y;
for (; box[x1 - 1][y1] == i; x1--)
;
for (; box[x1][y1 - 1] == i; y1--)
;
int x2 = x, y2 = y;
for (; box[x2 + 1][y2] == i; x2++)
;
for (; box[x2][y2 + 1] == i; y2++)
;
// mp1.insert({{x1, y1}, {y2 - y1 + 1, x2 - x1 + 1}});
vc1[x1][y1] = {y2 - y1 + 1, x2 - x1 + 1};
// mp2.insert({{x2, y2}, {y2 - y1 + 1, x2 - x1 + 1}});
vc2[x2][y2] = {y2 - y1 + 1, x2 - x1 + 1};
q.push({x1, y1, y2 - y1 + 1, x2 - x1 + 1});
}
while (q.size())
{
auto [ux, uy, w, h] = q.front();
q.pop();
// right
if (check(ux, uy + w, 1))
{
auto [w1, h1] = vc1[ux][uy + w];
if (h1 == h)
{
q.push({ux, uy, w + w1, h});
// mp1.erase({ux, uy});
vc1[ux][uy] = {-1, -1};
// mp1.erase({ux, uy + w});
vc1[ux][uy + w] = {-1, -1};
// mp2.erase({ux + h - 1, uy + w - 1});
vc2[ux + h - 1][uy + w - 1] = {-1, -1};
// mp2.erase({ux + h1 - 1, uy + w + w1 - 1});
vc2[ux + h1 - 1][uy + w + w1 - 1] = {-1, -1};
// mp1.insert({{ux, uy}, {w + w1, h}});
vc1[ux][uy] = {w + w1, h};
// mp2.insert({{ux + h - 1, uy + w + w1 - 1}, {w + w1, h}});
vc2[ux + h - 1][uy + w + w1 - 1] = {w + w1, h};
continue;
}
}
// if (mp1.contains({ux, uy + w}))
// {
// auto [w1, h1] = mp1[{ux, uy + w}];
// if (h1 == h)
// {
// q.push({ux, uy, w + w1, h});
// mp1.erase({ux, uy});
// mp1.erase({ux, uy + w});
// mp2.erase({ux + h - 1, uy + w - 1});
// mp2.erase({ux + h1 - 1, uy + w + w1 - 1});
// mp1.insert({{ux, uy}, {w + w1, h}});
// mp2.insert({{ux + h - 1, uy + w + w1 - 1}, {w + w1, h}});
// continue;
// }
// }
// down
if (check(ux + h, uy, 1))
{
auto [w1, h1] = vc1[ux + h][uy];
if (w1 == w)
{
q.push({ux, uy, w, h + h1});
// mp1.erase({ux, uy});
vc1[ux][uy] = {-1, -1};
// mp1.erase({ux + h, uy});
vc1[ux + h][uy] = {-1, -1};
// mp2.erase({ux + h - 1, uy + w - 1});
vc2[ux + h - 1][uy + w - 1] = {-1, -1};
// mp2.erase({ux + h + h1 - 1, uy + w - 1});
vc2[ux + h + h1 - 1][uy + w - 1] = {-1, -1};
// mp1.insert({{ux, uy}, {w, h + h1}});
vc1[ux][uy] = {w, h + h1};
// mp2.insert({{ux + h + h1 - 1, uy + w - 1}, {w, h + h1}});
vc2[ux + h + h1 - 1][uy + w - 1] = {w, h + h1};
continue;
}
}
// if (mp1.contains({ux + h, uy}))
// {
// auto [w1, h1] = mp1[{ux + h, uy}];
// if (w1 == w)
// {
// q.push({ux, uy, w, h + h1});
// mp1.erase({ux, uy});
// mp1.erase({ux + h, uy});
// mp2.erase({ux + h - 1, uy + w - 1});
// mp2.erase({ux + h + h1 - 1, uy + w - 1});
// mp1.insert({{ux, uy}, {w, h + h1}});
// mp2.insert({{ux + h + h1 - 1, uy + w - 1}, {w, h + h1}});
// continue;
// }
// }
// left
if (check(ux + h - 1, uy - 1, 0))
{
auto [w1, h1] = vc2[ux + h - 1][uy - 1];
if (h1 == h)
{
q.push({ux, uy - w1, w1 + w, h});
// mp1.erase({ux, uy});
vc1[ux][uy] = {-1, -1};
// mp1.erase({ux, uy - w1});
vc1[ux][uy - w1] = {-1, -1};
// mp2.erase({ux + h - 1, uy + w - 1});
vc2[ux + h - 1][uy + w - 1] = {-1, -1};
// mp2.erase({ux + h - 1, uy - 1});
vc2[ux + h - 1][uy - 1] = {-1, -1};
// mp1.insert({{ux, uy - w1}, {w + w1, h}});
vc1[ux][uy - w1] = {w + w1, h};
// mp2.insert({{ux + h - 1, uy + w - 1}, {w + w1, h}});
vc2[ux + h - 1][uy + w - 1] = {w + w1, h};
continue;
}
}
// if (mp2.contains({ux + h - 1, uy - 1}))
// {
// auto [w1, h1] = mp2[{ux + h - 1, uy - 1}];
// if (h1 == h)
// {
// q.push({ux, uy - w1, w1 + w, h});
// mp1.erase({ux, uy});
// mp1.erase({ux, uy - w1});
// mp2.erase({ux + h - 1, uy + w - 1});
// mp2.erase({ux + h - 1, uy - 1});
// mp1.insert({{ux, uy - w1}, {w + w1, h}});
// mp2.insert({{ux + h - 1, uy + w - 1}, {w + w1, h}});
// continue;
// }
// }
// up
if (check(ux - 1, uy + w - 1, 0))
{
auto [w1, h1] = vc2[ux - 1][uy + w - 1];
if (w1 == w)
{
q.push({ux - h1, uy, w, h1 + h});
// mp1.erase({ux, uy});
vc1[ux][uy] = {-1, -1};
// mp1.erase({ux - h1, uy});
vc1[ux - h1][uy] = {-1, -1};
// mp2.erase({ux + h - 1, uy + w - 1});
vc2[ux + h - 1][uy + w - 1] = {-1, -1};
// mp2.erase({ux - 1, uy + w - 1});
vc2[ux - 1][uy + w - 1] = {-1, -1};
// mp1.insert({{ux - h1, uy}, {w, h + h1}});
vc1[ux - h1][uy] = {w, h + h1};
// mp2.insert({{ux + h - 1, uy + w - 1}, {w, h + h1}});
vc2[ux + h - 1][uy + w - 1] = {w, h + h1};
continue;
}
}
// if (mp2.contains({ux - 1, uy + w - 1}))
// {
// auto [w1, h1] = mp2[{ux - 1, uy + w - 1}];
// if (w1 == w)
// {
// q.push({ux - h1, uy, w, h1 + h});
// mp1.erase({ux, uy});
// mp1.erase({ux - h1, uy});
// mp2.erase({ux + h - 1, uy + w - 1});
// mp2.erase({ux - 1, uy + w - 1});
// mp1.insert({{ux - h1, uy}, {w, h + h1}});
// mp2.insert({{ux + h - 1, uy + w - 1}, {w, h + h1}});
// continue;
// }
// }
}
// cerr << vc1[1][1].first << ' ' << vc1[1][1].second << '\n';
if (check(1, 1, 1))
{
auto [w, h] = vc1[1][1];
if (w == m && h == n)
{
cout << "YES" << '\n';
}
else
{
cout << "NO" << '\n';
}
}
// cerr << "ok" << '\n';
// for (auto [x, y] : mp1)
// {
// auto [_x, _y] = x;
// auto [__x, __y] = y;
// cerr << _x << ' ' << _y << " " << __x << " " << __y << '\n';
// }
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: -100
Time Limit Exceeded
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...