#include <bits/stdc++.h>
#define MAXN 1010
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int N, M, C[MAXN][MAXN], vis[MAXN][MAXN];
set<pii> s[2*MAXN];
void clean(int X, int Y) {
vis[X][Y] = 1;
s[X+Y].erase({X, Y});
if(vis[X+1][Y-1]) {
if(!vis[X+1][Y]) clean(X+1, Y);
if(!vis[X][Y-1]) clean(X, Y-1);
} if(vis[X-1][Y+1]) {
if(!vis[X][Y+1]) clean(X, Y+1);
if(!vis[X-1][Y]) clean(X-1, Y);
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> N >> M;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
cin >> C[i][j];
if(C[i][j] == 0) s[i+j].insert({i, j});
else vis[i][j] = 1;
}
}
for(int i = 0; i <= N+1; i++) vis[i][0] = vis[i][M+1] = 1;
for(int i = 0; i <= M+1; i++) vis[0][i] = vis[N+1][i] = 1;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
if((i == 1 && j == 1) || (i == N && j == M)) continue;
if(!vis[i][j] && ((vis[i+1][j] && vis[i][j+1]) || (vis[i-1][j] && vis[i][j-1]))) clean(i, j);
}
}
int Q; cin >> Q;
while(Q--) {
int X, Y; cin >> X >> Y;
if(vis[X][Y]) {
cout << 1 << '\n';
C[X][Y] = 1;
} else {
if(s[X+Y].size() == 1) {
cout << 0 << '\n';
} else {
clean(X, Y);
cout << 1 << '\n';
}
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1220 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
4 ms |
1484 KB |
Output is correct |
4 |
Correct |
7 ms |
1632 KB |
Output is correct |
5 |
Correct |
7 ms |
1696 KB |
Output is correct |
6 |
Correct |
9 ms |
1776 KB |
Output is correct |
7 |
Correct |
6 ms |
1740 KB |
Output is correct |
8 |
Correct |
7 ms |
1784 KB |
Output is correct |
9 |
Correct |
6 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1220 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
4 ms |
1484 KB |
Output is correct |
4 |
Correct |
7 ms |
1632 KB |
Output is correct |
5 |
Correct |
7 ms |
1696 KB |
Output is correct |
6 |
Correct |
9 ms |
1776 KB |
Output is correct |
7 |
Correct |
6 ms |
1740 KB |
Output is correct |
8 |
Correct |
7 ms |
1784 KB |
Output is correct |
9 |
Correct |
6 ms |
1740 KB |
Output is correct |
10 |
Correct |
23 ms |
3532 KB |
Output is correct |
11 |
Correct |
5 ms |
1356 KB |
Output is correct |
12 |
Correct |
842 ms |
54624 KB |
Output is correct |
13 |
Correct |
388 ms |
45696 KB |
Output is correct |
14 |
Correct |
980 ms |
56788 KB |
Output is correct |
15 |
Correct |
1002 ms |
57288 KB |
Output is correct |
16 |
Correct |
805 ms |
61736 KB |
Output is correct |
17 |
Correct |
869 ms |
64992 KB |
Output is correct |
18 |
Correct |
914 ms |
63340 KB |
Output is correct |
19 |
Correct |
811 ms |
66884 KB |
Output is correct |
20 |
Correct |
694 ms |
66892 KB |
Output is correct |
21 |
Correct |
861 ms |
66984 KB |
Output is correct |