Submission #1179812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179812		NAMIN	Furniture (JOI20_furniture)	C++20	0 / 100	5095 ms	1092 KiB

furniture

#include <bits/stdc++.h>

#define endl "\n"
#define ll long long

using namespace std;

const int mxN = 1004;
int N,M;
int G[mxN][mxN];
int coli[mxN][mxN][4];
vector<int> depy{-1,0,1,0,1,-1,1};
vector<int> depx{0,-1,0,1,1,1,-1};

bool ok(int x,int y){
	return x >= 0 && x < M && y >= 0 && y < N;
}

void dfs(int x,int y,int val){
	if(coli[y][x][val])
		return;
	coli[y][x][val] = 1;

	for(int d=0;d<7;d++){
		int dx = x+depx[d],dy = y+depy[d];
		if(!ok(dx,dy))
			continue;
		if(!G[dy][dx])
			continue;

		dfs(dx,dy,val);
	}
}

void fill(int x,int y){
	if(!ok(x,y))
		return;
	bool canright =true,candown=true;
	if(x==M-1)
		canright = false;
	else if(G[y][x+1])
		canright = false;
	if(y == N-1)
		candown = false;
	else if(G[y+1][x])
		candown = false;

	if(!canright && !candown){
		G[y][x] = 1;
		fill(x-1,y);
		if(ok(x,y-1) && G[y-1][x]){
			fill(x,y-1);
		}
	}
}

void solve(){
	int left = 3,right = 1,up = 0,down=2;
	cin >> N >> M;

	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			for(int k=0;k<4;k++){
				coli[i][j][k] = 0;
			}
		}
	}

	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			cin >> G[i][j];
		}
	}

	for(int i=N-1;i>=0;i--){
		for(int j=M-2;j>=0;j--){
			if(G[i][j])
				continue;
			bool canright =true,candown=true;
			if(j==M-1)
				canright = false;
			else if(G[i][j+1])
				canright = false;
			if(i == N-1)
				candown = false;
			else if(G[i+1][j])
				candown = false;

			if(!canright && !candown){
				G[i][j] = 1;
			}
		}
	}
	
	for(int i=0;i<N;i++){
		if(!coli[i][0][left] && G[i][0])
			dfs(0,i,left);
		if(!coli[i][M-1][right] && G[i][M-1])
			dfs(M-1,i,right);
	}
	for(int i=0;i<M;i++){
		if(!coli[0][i][up] && G[0][i])
			dfs(i,0,up);
		if(!coli[N-1][i][down] && G[N-1][i])
			dfs(i,N-1,down);
	}

	int Q;
	cin >> Q;

	while(Q--){
		int y,x;
		cin >> y >> x;
		y--,x--;

		vector<int> curcoli(4,0);
		if(y == N-1)
			curcoli[down] = true;
		if(y == 0)
			curcoli[up] = true;
		if(x == 0)
			curcoli[left] = true;
		if(x == M-1)
			curcoli[right] = true;

		for(int d=0;d<7;d++){
			int dx = x+depx[d],dy = y+depy[d];
			if(!ok(dx,dy))
				continue;
			if(!G[dy][dx])
				continue;
			for(int k=0;k<4;k++){
				curcoli[k] |= coli[dy][dx][k];
			}
		}
		
		bool can = true;
		if(curcoli[left] && curcoli[up])
			can = false;
		else if(curcoli[left] && curcoli[right])
			can = false;
		else if(curcoli[down] && curcoli[up])
			can = false;
		else if(curcoli[right] && curcoli[down])
			can = false;

		if(can){
			cout << 1 << endl;
			G[y][x] = 1;
			
			fill(x-1,y);
			if(ok(x,y-1) && G[y-1][x])
				fill(x,y-1);

			for(int k=0;k<4;k++){
				if(curcoli[k]){
					dfs(x,y,k);
				}
			}
		}
		else{
			cout << 0 << endl;
		}
	}

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

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