QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412758 | #6746. Merge the Rectangles | p | WA | 88ms | 195468kb | C++14 | 3.0kb | 2024-05-16 19:00:42 | 2024-05-16 19:00:43 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N = 2e3;
char ma[N][N];
struct node
{
int fg;
int pos;
int l, r;
bool operator<(const node &o) const
{
if (fg != o.fg)
return fg < o.fg;
if (pos != o.pos)
return pos < o.pos;
if (l != o.l)
return l < o.l;
return r < o.r;
}
};
map<node, int> num;
vector<node> arr[2][N][N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
cin >> ma[i][j];
for (int i = 1; i < n; i++)
{
int l = -1;
for (int j = 1; j <= m + 1; j++)
{
if (j == m + 1 || ma[i][j] == '0')
{
if (l != -1)
{
node t = {1, i, l, j - 1};
num[t] = 2;
arr[1][i][j - 1].push_back(t);
arr[1][i][l].push_back(t);
}
l = -1;
}
else if (l == -1)
l = j - 1;
}
}
memset(0, sizeof ma, 0);
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++)
cin >> ma[i][j];
for (int j = 1; j < m; j++)
{
int l = -1;
for (int i = 1; i <= n + 1; i++)
{
if (i == n + 1 || ma[i][j] == '0')
{
if (l != -1)
{
node t = {0, j, l, i - 1};
num[t] = 2;
arr[0][l][j].push_back(t);
arr[0][i - 1][j].push_back(t);
}
l = -1;
}
else if (l == -1)
l = i - 1;
}
}
queue<node> que;
node t = {1, 0, 0, m};
que.push(t);
t = {1, n, 0, m};
que.push(t);
t = {0, 0, 0, n};
que.push(t);
t = {0, m, 0, n};
que.push(t);
while (que.size())
{
node t = que.front();
que.pop();
int pos = t.pos;
for (int i = t.l; i <= t.r; i++)
{
int x, y;
if (t.fg == 0)
x = i, y = pos;
else
x = pos, y = i;
for (auto c : arr[t.fg ^ 1][x][y])
{
if (num[c])
{
num[c]--;
if (num[c] == 0)
que.push(c);
}
}
}
}
for (auto c : num)
{
// cout << c.first.fg << " " << c.first.pos << " " << c.first.l << "|" << c.first.r << " ";
if (c.second > 0)
{
cout << "NO\n";
return 0;
// cout << "!";
}
// cout << "\n";
}
cout << "YES\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 193276kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 20ms
memory: 192376kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 65ms
memory: 194408kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 72ms
memory: 194608kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 56ms
memory: 194396kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 76ms
memory: 194144kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 80ms
memory: 194272kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #8:
score: 0
Accepted
time: 60ms
memory: 194392kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #9:
score: 0
Accepted
time: 55ms
memory: 195292kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 88ms
memory: 195468kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #11:
score: 0
Accepted
time: 70ms
memory: 195200kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #12:
score: -100
Wrong Answer
time: 52ms
memory: 194744kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
wrong answer expected YES, found NO