Submission #392344

#TimeUsernameProblemLanguageResultExecution timeMemory
392344lukameladzeFurniture (JOI20_furniture)C++14
0 / 100
7 ms1996 KiB
# include <bits/stdc++.h> #define f first #define s second #define pb push_back using namespace std; const int N=1005; long long n,m,fix[3][N][N],x,y,a,b,aa[N][N],mp[3*N],r[N][N],qq,ans[1000*N]; queue< pair <int ,int > > q; int check1(int x, int y) { if((y==1 || r[x][y-1]==1) && (x==1 || r[x-1][y]==1)) return 1; else return 0; } int check2(int x, int y) { if((y==m ||r[x][y+1]==1) && (x==n || r[x+1][y]==1)) return 1; else return 0; } int check(int x, int y) { if (x>n || y>m || x<1 || y<1) return 0; else return 1; } void go(int a, int b, int ty) { if (fix[ty+1][a][b]==1) return; fix[ty+1][a][b]=1; if (check(a+ty,b) && aa[a+ty][b]==0) go(a+ty,b,ty); if (check(a,ty+b) && aa[a][ty+b]==0) go(a,ty+b,ty); } void update1(int a,int b){ x=a; y=b; if(check(x+1,y) && r[x+1][y]==0 && r[x+1][y-1]==1) q.push({x+1,y}); if(check(x,y+1) && r[x][y+1]==0 && r[x-1][y+1]==1) q.push({x,y+1}); while(q.size()){ x=q.front().f; y=q.front().s; q.pop(); if(r[x][y-1]==0 || r[x-1][y]==0) continue; r[x][y]=1; mp[x+y]--; if(check(x+1,y) && r[x+1][y]==0 && r[x+1][y-1]==1) q.push({x+1,y}); if(check(x,y+1) && r[x][y+1]==0 && r[x-1][y+1]==1) q.push({x,y+1}); } } void update2(int a,int b){ x=a; y=b; if(check(x-1,y) && r[x-1][y]==0 && 1==r[x-1][y+1]) q.push({x-1,y}); if(check(x,y-1) && r[x][y-1]==0 && 1==r[x+1][y-1]) q.push({x,y-1}); while(q.size()){ x=q.front().f; y=q.front().s; q.pop(); if(r[x][y+1]==0 || r[x+1][y]==0) continue; r[x][y]=1; mp[x+y]--; if(check(x-1,y) && r[x-1][y]==0 && 1==r[x-1][y+1]) q.push({x-1,y}); if(check(x,y-1) && r[x][y-1]==0 && 1==r[x+1][y-1]) q.push({x,y-1}); } } int main() { std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { cin>>aa[i][j]; } } go(1,1,1); go(n,m,-1); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { if (fix[0][i][j] && fix[2][i][j]) { r[i][j]=0; mp[i+j]++; } else r[i][j]=1; } } cin>>qq; for (int i=1; i<=qq; i++) { cin>>x>>y; if (r[x][y]==1) { ans[i]=1; continue; } if (mp[x+y]==1) { ans[i]=0; continue; } ans[i]=1; mp[x+y]--; r[x][y]=1; update1(x,y); update2(x,y); } for (int i=1; i<=qq; i++) cout<<ans[i]<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...