# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
294438 | 2020-09-08T23:01:32 Z | ChrisT | Furniture (JOI20_furniture) | C++17 | 466 ms | 17920 KB |
#include <bits/stdc++.h> using namespace std; const int MN = 1e3+5, MOD = 1e9 + 7, BASE = 143; bool canL[MN][MN], canR[MN][MN]; int a[MN][MN], cnt[MN * 2]; int main () { int n,m; scanf ("%d %d",&n,&m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf ("%d",&a[i][j]); canL[i][j] = !a[i][j] && (i*j==1 || canL[i-1][j] || canL[i][j-1]); } } for (int i = n; i >= 1; i--) { for (int j = m; j >= 1; j--) { canR[i][j] = !a[i][j] && ((i==n&&j==m)||canR[i+1][j]||canR[i][j+1]); cnt[i+j] += canR[i][j] && canL[i][j]; } } function<void(int,int)> fixL = [&] (int x, int y) { if (x > n || y > m || !canL[x][y] || (canL[x][y] = canL[x-1][y] || canL[x][y-1])) return; cnt[x+y] -= canR[x][y]; fixL(x+1,y); fixL(x,y+1); }; function<void(int,int)> fixR = [&] (int x, int y) { if (x <= 0 || y <= 0 || !canR[x][y] || (canR[x][y] = canR[x+1][y] || canR[x][y+1])) return; cnt[x+y] -= canL[x][y]; fixR(x-1,y); fixR(x,y-1); }; int q; scanf ("%d",&q); while (q--) { int x,y; scanf ("%d %d",&x,&y); if (!(canL[x][y] && canR[x][y])) {printf ("1\n"); continue;} if (cnt[x+y] == 1) {printf ("0\n"); continue;} canL[x][y] = canR[x][y] = 0; --cnt[x+y]; fixR(x-1,y); fixR(x,y-1); fixL(x+1,y); fixL(x,y+1); printf ("1\n"); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 768 KB | Output is correct |
2 | Correct | 2 ms | 896 KB | Output is correct |
3 | Correct | 3 ms | 896 KB | Output is correct |
4 | Correct | 4 ms | 1024 KB | Output is correct |
5 | Correct | 4 ms | 1024 KB | Output is correct |
6 | Correct | 5 ms | 1024 KB | Output is correct |
7 | Correct | 5 ms | 1024 KB | Output is correct |
8 | Correct | 5 ms | 1024 KB | Output is correct |
9 | Correct | 5 ms | 1024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 768 KB | Output is correct |
2 | Correct | 2 ms | 896 KB | Output is correct |
3 | Correct | 3 ms | 896 KB | Output is correct |
4 | Correct | 4 ms | 1024 KB | Output is correct |
5 | Correct | 4 ms | 1024 KB | Output is correct |
6 | Correct | 5 ms | 1024 KB | Output is correct |
7 | Correct | 5 ms | 1024 KB | Output is correct |
8 | Correct | 5 ms | 1024 KB | Output is correct |
9 | Correct | 5 ms | 1024 KB | Output is correct |
10 | Correct | 13 ms | 1024 KB | Output is correct |
11 | Correct | 5 ms | 768 KB | Output is correct |
12 | Correct | 231 ms | 10872 KB | Output is correct |
13 | Correct | 104 ms | 7800 KB | Output is correct |
14 | Correct | 397 ms | 15608 KB | Output is correct |
15 | Correct | 428 ms | 15864 KB | Output is correct |
16 | Correct | 404 ms | 16760 KB | Output is correct |
17 | Correct | 435 ms | 17432 KB | Output is correct |
18 | Correct | 430 ms | 17224 KB | Output is correct |
19 | Correct | 466 ms | 17920 KB | Output is correct |
20 | Correct | 404 ms | 17888 KB | Output is correct |
21 | Correct | 436 ms | 17884 KB | Output is correct |