# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
296920 | 2020-09-11T05:02:37 Z | nafis_shifat | Furniture (JOI20_furniture) | C++14 | 550 ms | 19748 KB |
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> using namespace std; const int mxn=1e5+5; const int inf=1e9; int a[1002][1002]={}; int cnt[3000]={}; int di[]={0,0,-1,1}; int dj[]={-1,1,0,0}; bool f=false; int n,m; vector<pii> v; void dfs(int i,int j) { if(a[i][j]) return; int v1=a[i][j+1]+a[i+1][j]; int v2=a[i-1][j]+a[i][j-1]; if(v1!=2 && v2!=2) return; a[i][j]=1; cnt[i+j]--; v.push_back({i,j}); if(i==1 && j==1) { a[i][j]=0; if(v1==2) { f=true; } return; } if(i==n && j==m) { a[i][j]=0; if(v2==2) { f=true; } return; } for(int k=0;k<4;k++) { int ii=i+di[k]; int jj=j+dj[k]; dfs(ii,jj); } } int main() { cin>>n>>m; for(int i=0;i<=m+1;i++) { a[0][i]=1; a[n+1][i]=1; } for(int i=0;i<=n+1;i++) { a[i][0]=a[i][m+1]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cnt[i+j]++; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x; scanf("%d",&x); if(!x) continue; a[i][j]=x; for(int k=0;k<4;k++) { int ii=i+di[k]; int jj=j+dj[k]; dfs(ii,jj); } } } int q; cin>>q; while(q--) { v.clear(); int i,j; scanf("%d%d",&i,&j); if(a[i][j]==1) { printf("1\n"); continue; } if(cnt[i+j]==1) { printf("0\n"); continue; } f=false; a[i][j]=1; cnt[i+j]--; for(int k=0;k<4;k++) { int ii=i+di[k]; int jj=j+dj[k]; dfs(ii,jj); } if(f) { printf("0\n"); a[i][j]=0; cnt[i+j]++; for(pii x:v) { a[x.first][x.second]=0; cnt[x.first+x.second]++; } } else { printf("1\n"); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 640 KB | Output is correct |
2 | Correct | 3 ms | 896 KB | Output is correct |
3 | Correct | 3 ms | 768 KB | Output is correct |
4 | Correct | 5 ms | 896 KB | Output is correct |
5 | Correct | 6 ms | 1024 KB | Output is correct |
6 | Correct | 5 ms | 896 KB | Output is correct |
7 | Correct | 5 ms | 896 KB | Output is correct |
8 | Correct | 5 ms | 896 KB | Output is correct |
9 | Correct | 5 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 640 KB | Output is correct |
2 | Correct | 3 ms | 896 KB | Output is correct |
3 | Correct | 3 ms | 768 KB | Output is correct |
4 | Correct | 5 ms | 896 KB | Output is correct |
5 | Correct | 6 ms | 1024 KB | Output is correct |
6 | Correct | 5 ms | 896 KB | Output is correct |
7 | Correct | 5 ms | 896 KB | Output is correct |
8 | Correct | 5 ms | 896 KB | Output is correct |
9 | Correct | 5 ms | 896 KB | Output is correct |
10 | Correct | 26 ms | 1532 KB | Output is correct |
11 | Correct | 5 ms | 640 KB | Output is correct |
12 | Correct | 251 ms | 10092 KB | Output is correct |
13 | Correct | 111 ms | 8036 KB | Output is correct |
14 | Correct | 550 ms | 14700 KB | Output is correct |
15 | Correct | 420 ms | 14324 KB | Output is correct |
16 | Correct | 437 ms | 14852 KB | Output is correct |
17 | Correct | 475 ms | 15608 KB | Output is correct |
18 | Correct | 441 ms | 15352 KB | Output is correct |
19 | Correct | 488 ms | 17508 KB | Output is correct |
20 | Correct | 418 ms | 19748 KB | Output is correct |
21 | Correct | 456 ms | 17892 KB | Output is correct |