Submission #392344

#	Time	Username	Problem	Language	Result	Execution time	Memory
392344		lukameladze	Furniture (JOI20_furniture)	C++14	0 / 100	7 ms	1996 KiB

furniture

# 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;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95