#include <iostream>
#include <vector>
using namespace std;
const int MX = 1'000;
int N, M;
vector< vector<int> > C(1+MX+1, vector<int>(1+MX+1, 1));
vector<int> ct(1+3*MX, 0);
vector<int> sz(1+3*MX, 0);
void fwd(int x, int y)
{
// cerr << "fwd " << x << ' ' << y << '\n';
if(x+1 <= N && C[x+1][y-1] && !C[x+1][y])
{
ct[x+y+1]++;
C[x+1][y] = 1;
fwd(x+1, y);
}
// cerr << (y+1 <= M) << ' ' << C[x-1][y+1] << ' ' << !C[x][y+1] << '\n';
if(y+1 <= M && C[x-1][y+1] && !C[x][y+1])
{
ct[x+y+1]++;
C[x][y+1] = 1;
fwd(x, y+1);
}
}
void bwd(int x, int y)
{
if(1 <= x-1 && C[x-1][y+1] && !C[x-1][y])
{
ct[x+y-1]++;
C[x-1][y] = 1;
bwd(x-1, y);
}
if(1 <= y-1 && C[x+1][y-1] && !C[x][y-1])
{
ct[x+y-1]++;
C[x][y-1] = 1;
bwd(x, y-1);
}
}
int main()
{
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]) ct[i+j]++;
sz[i+j]++;
}
}
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
if(C[i][j])
{
fwd(i, j);
bwd(i, j);
}
// cerr << ct[1+1] << '\n';
//
// cerr << "init:\n";
// for(int i = 0; i <= N+1; i++)
// {
// for(int j = 0; j <= M+1; j++)
// {
// cerr << C[i][j] << ' ';
// }
// cerr << '\n';
// }
// cerr << "\n\n";
int Q;
cin >> Q;
for(int q = 1; q <= Q; q++)
{
int X, Y;
cin >> X >> Y;
// cerr << ct[X+Y] + 1 << ' ' << sz[X+Y] << '\n';
if(C[X][Y] == 1)
{
cout << "1\n";
}
else if(ct[X+Y] + 1 == sz[X+Y])
{
cout << "0\n";
continue;
}
else
{
cout << "1\n";
C[X][Y] = 1;
ct[X+Y]++;
fwd(X, Y);
bwd(X, Y);
}
// cerr << "after update: ";
// for(int i = 0; i <= N+1; i++)
// {
// for(int j = 0; j <= M+1; j++)
// {
// cerr << C[i][j] << ' ';
// }
// cerr << '\n';
// }
// cerr << "\n\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4284 KB |
Output is correct |
2 |
Correct |
11 ms |
4312 KB |
Output is correct |
3 |
Correct |
12 ms |
4300 KB |
Output is correct |
4 |
Correct |
20 ms |
4300 KB |
Output is correct |
5 |
Correct |
23 ms |
4292 KB |
Output is correct |
6 |
Correct |
25 ms |
4332 KB |
Output is correct |
7 |
Correct |
25 ms |
4292 KB |
Output is correct |
8 |
Correct |
25 ms |
4352 KB |
Output is correct |
9 |
Correct |
24 ms |
4380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4284 KB |
Output is correct |
2 |
Correct |
11 ms |
4312 KB |
Output is correct |
3 |
Correct |
12 ms |
4300 KB |
Output is correct |
4 |
Correct |
20 ms |
4300 KB |
Output is correct |
5 |
Correct |
23 ms |
4292 KB |
Output is correct |
6 |
Correct |
25 ms |
4332 KB |
Output is correct |
7 |
Correct |
25 ms |
4292 KB |
Output is correct |
8 |
Correct |
25 ms |
4352 KB |
Output is correct |
9 |
Correct |
24 ms |
4380 KB |
Output is correct |
10 |
Correct |
76 ms |
4672 KB |
Output is correct |
11 |
Correct |
17 ms |
4428 KB |
Output is correct |
12 |
Correct |
824 ms |
8972 KB |
Output is correct |
13 |
Correct |
198 ms |
6088 KB |
Output is correct |
14 |
Correct |
1939 ms |
13692 KB |
Output is correct |
15 |
Correct |
2063 ms |
13988 KB |
Output is correct |
16 |
Correct |
2198 ms |
14864 KB |
Output is correct |
17 |
Correct |
2263 ms |
15468 KB |
Output is correct |
18 |
Correct |
2295 ms |
15204 KB |
Output is correct |
19 |
Correct |
2322 ms |
15972 KB |
Output is correct |
20 |
Correct |
2269 ms |
15916 KB |
Output is correct |
21 |
Correct |
2357 ms |
15828 KB |
Output is correct |