Submission #296089

#	Time	Username	Problem	Language	Result	Execution time	Memory
296089		groeneprof	Furniture (JOI20_furniture)	C++14	100 / 100	3661 ms	28192 KiB

furniture

#include <bits/stdc++.h>

#define P(a) do{if(debug) cout<<a<<endl;} while(false)
#define H(a) P(#a<<": "<<a)
#define FR(i,a,b) for(int i = (a); i<(int)((b)); i++)
#define F(i,n) FR(i,0,n)
const int debug = 0;

using namespace std;

int n,m,Q;

bool inbounds(int x,int y){
	return x>=0 && x<n && y>=0 && y<m;
}


vector<vector<int> > C;
vector<vector<int> > A;
vector<vector<int> > B;
vector<vector<int> > D;
vector<int> vx,vy;
void updateB(int x, int y){
	if(!inbounds(x,y) || B[x][y] == 1){
		return;
	}
	if(C[x][y] == 1 || !((inbounds(x-1,y) && B[x-1][y]==0) || (inbounds(x,y-1) && B[x][y-1]==0))) {
		B[x][y] = 1;
		updateB(x+1,y);
		updateB(x,y+1);
	}

}

void updateA(int x, int y){
	if(!inbounds(x,y) || A[x][y] == 1){
		return;
	}
	if(C[x][y] == 1 || !((inbounds(x+1,y) && A[x+1][y]==0) || (inbounds(x,y+1) && A[x][y+1]==0))) {
		A[x][y] = 1;
		updateA(x-1,y);
		updateA(x,y-1);
	}

}


bool to00(int x, int y,vector<pair<int,int> >& path){
	if(!inbounds(x,y) || B[x][y] == 1) return false;
	path.push_back({x,y});
	if(rand()%2){
		if(inbounds(x-1,y) && B[x-1][y] == 0) {
			to00(x-1,y,path); 
			return true;
		}
		if(inbounds(x,y-1) && B[x][y-1] == 0) {
			to00(x,y-1,path); 
			return true;
		}
		return false;
	}
	else {
		if(inbounds(x,y-1) && B[x][y-1] == 0) {
			to00(x,y-1,path); 
			return true;
		}
		if(inbounds(x-1,y) && B[x-1][y] == 0) {
			to00(x-1,y,path); 
			return true;
		}
		return false;
	}
}

bool tonm(int x, int y,vector<pair<int,int> >& path){
	if(!inbounds(x,y) || A[x][y] == 1) return false;
	path.push_back({x,y});
	if(rand()%2){
		if(inbounds(x+1,y) && A[x+1][y] == 0) {
			tonm(x+1,y,path); 
			return true;
		}
		if(inbounds(x,y+1) && A[x][y+1] == 0) {
			tonm(x,y+1,path); 
			return true;
		}
		return false;
	}
	else {
		if(inbounds(x,y+1) && A[x][y+1] == 0) {
			tonm(x,y+1,path); 
			return true;
		}
		if(inbounds(x+1,y) && A[x+1][y] == 0) {
			tonm(x+1,y,path); 
			return true;
		}
		return false;
	}
}


int main(){
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	cin>>n>>m;
	A.resize(n+1,vector<int> (m+1,0));
	B.resize(n+1,vector<int> (m+1,0));
	C.resize(n+1,vector<int> (m+1,0));
	D.resize(n+1,vector<int> (m+1,0));
	F(i,n) F(j,m){
		cin>>C[i][j];
	}

	F(i,n) F(j,m) {
		if(i!=0||j!=0) B[i][j] = 1;
		if(inbounds(i,j-1) && B[i][j-1]==0) B[i][j] = 0;
		if(inbounds(i-1,j) && B[i-1][j]==0) B[i][j] = 0;
		if(C[i][j] == 1) B[i][j] = 1;
	}
	for(int i = n-1; i>=0; i--) for(int j = m-1; j>=0; j--) {
		if(i!=n-1||j!=m-1) A[i][j] = 1;
		if(inbounds(i,j+1) && A[i][j+1]==0) A[i][j] = 0;
		if(inbounds(i+1,j) && A[i+1][j]==0) A[i][j] = 0;
		if(C[i][j] == 1) A[i][j] = 1;
	}

	vector<pair<int,int> > path;
	tonm(0,0,path);
	for(pair<int,int> pii : path){
		D[pii.first][pii.second] = 1;
	}
	if(debug){
		P("B");
		F(i,n){
			F(j,m){
				cout<<B[i][j]<<" ";
			}
			cout<<endl;
		}
		P("A");
		F(i,n){
			F(j,m){
				cout<<A[i][j]<<" ";
			}
			cout<<endl;
		}
		P("D");
		F(i,n){
			F(j,m){
				cout<<D[i][j]<<" ";
			}
			cout<<endl;
		}
	}
	bool boool = true;
	cin>>Q;
	F(q,Q){
		vx.clear();
		vy.clear();
		int x,y;
		cin>>x>>y;
		x--;
		y--;
		if(D[x][y]==0){
			C[x][y] = 1;
			updateB(x,y);
			updateA(x,y);
			//cout<<"a";
			cout<<1-B[n-1][m-1]<<endl;
			if(B[n-1][m-1] == 1) {
				if(debug){
					boool = false;
					cout<<"B: "<<endl;
					F(i,n){
						F(j,m){
							cout<<B[i][j]<<" ";
						}
						cout<<endl;
					}
					cout<<"A"<<endl;
					P("A");
					F(i,n){
						F(j,m){
							cout<<A[i][j]<<" ";
						}
						cout<<endl;
					}
					cout<<"D"<<endl;
					P("D");
					F(i,n){
						F(j,m){
							cout<<D[i][j]<<" ";
						}
						cout<<endl;
					}
					cout<<"C"<<endl;
					P("C");
					F(i,n){
						F(j,m){
							cout<<C[i][j]<<" ";
						}
						cout<<endl;
					}
				}
				F(i,vx.size()){
					B[vx[i]][vy[i]] = 0;
				}
				C[x][y] = 0;
			}
		}	 
		else{
			P("a");
			//cout<<"b";
			vector<pair<int,int> > path1;
			bool bol = false;
			F(i,x){
				if(inbounds(i,y+1) && A[i][y+1] == 0 && B[i][y+1] == 0){
					//vector<int> path1:
					to00(i,y+1,path1);
					tonm(i,y+1,path1);
					H(i);
					H(y+1);
					bol = true;
					break;
				}
			}
			if(!bol) FR(i,x+1,n){
				if(inbounds(i,y-1) && A[i][y-1] == 0 && B[i][y-1] == 0){
					//vector<int> path1;
					to00(i,y-1,path1);
					tonm(i,y-1,path1);
					H(i);
					H(y-1);
					bol = true;
					break;
				}
			}
			if(bol){
				cout<<1<<endl;
				C[x][y] = 1;
				updateA(x,y);
				updateB(x,y);
				for(pair<int,int> pii : path){
					D[pii.first][pii.second] = 0;
				}
				for(pair<int,int> pii : path1){
					D[pii.first][pii.second] = 1;
				}
				path = path1;
			}
			else{
				cout<<0<<endl;
			}
			if(debug){
					boool = false;
					cout<<"B: "<<endl;
					F(i,n){
						F(j,m){
							cout<<B[i][j]<<" ";
						}
						cout<<endl;
					}
					cout<<"A"<<endl;
					P("A");
					F(i,n){
						F(j,m){
							cout<<A[i][j]<<" ";
						}
						cout<<endl;
					}
					cout<<"D"<<endl;
					P("D");
					F(i,n){
						F(j,m){
							cout<<D[i][j]<<" ";
						}
						cout<<endl;
					}
					cout<<"C"<<endl;
					P("C");
					F(i,n){
						F(j,m){
							cout<<C[i][j]<<" ";
						}
						cout<<endl;
					}
				}

		}
		if(debug){
			P("B");
			F(i,n){
				F(j,m){
					cout<<B[i][j]<<" ";
				}
				cout<<endl;
			}
			P("A");
			F(i,n){
				F(j,m){
					cout<<A[i][j]<<" ";
				}
				cout<<endl;
			}
			P("D");
			F(i,n){
				F(j,m){
					cout<<D[i][j]<<" ";
				}
				cout<<endl;
			}
		}
	}

	return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:156:7: warning: variable 'boool' set but not used [-Wunused-but-set-variable]
  156 |  bool boool = true;
      |       ^~~~~

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