Submission #961768

#	Time	Username	Problem	Language	Result	Execution time	Memory
961768		pcc	Furniture (JOI20_furniture)	C++17	0 / 100	2 ms	4952 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1010;
bitset<mxn> dp[2][mxn];
bitset<mxn> able[mxn];
int N,M,Q;
set<pii> alive[mxn*2];
int arr[mxn][mxn];


namespace INIT{
	void GO(){
		dp[0][1][1] = dp[1][1][1] = 1;
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=M;j++){
				if(i==1&&j==1)continue;
				if(!arr[i][j])continue;
				dp[0][i][j] = (dp[0][i-1][j]|dp[0][i][j-1]);
			}
			for(int j = 1;j<=M;j++){
				if(i==1&&j==1)continue;
				if(!arr[N+1-i][M+1-j])continue;
				dp[1][i][j] = (dp[1][i-1][j]|dp[1][i][j-1]);
			}
		}
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=M;j++){
				if(dp[0][i][j]&&dp[1][N+1-i][M+1-j]){
					able[i][j] = true;
					alive[i+j].insert(pii(i,j));
				}
			}
		}
		return;
	}
}

namespace QUERY{
	queue<pii> q;
	void del(int sx,int sy){
		able[sx][sy] = false;
		alive[sx+sy].erase(pii(sx,sy));
		q.push(pii(sx,sy));
		while(!q.empty()){
			auto [r,c] = q.front();
			q.pop();
			alive[r+c].erase(pii(r,c));
			if(able[r+1][c]&&!able[r+1][c-1]){
				able[r+1][c] = false;
				alive[r+c+1].erase(pii(r+1,c));
				q.push(pii(r+1,c));
			}
			if(able[r][c+1]&&!able[r-1][c+1]){
				able[r][c+1] = false;
				alive[r+c+1].erase(pii(r,c+1));
				q.push(pii(r,c+1));
			}
			if(able[r][c-1]&&!able[r+1][c-1]){
				able[r][c-1] = false;
				alive[r+c-1].erase(pii(r,c-1));
				q.push(pii(r,c-1));
			}
			if(able[r-1][c]&&!able[r-1][c+1]){
				able[r-1][c] = false;
				alive[r+c-1].erase(pii(r-1,c));
				q.push(pii(r-1,c));
			}
		}
		return;
	}
	void solve(int r,int c){
		if(!able[r][c]){
			cout<<"1\n";
			return;
		}
		if(alive[r+c].size() == 1){
			cout<<"0\n";
			return;
		}
		cout<<"1\n";
		del(r,c);
		/*
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=M;j++)cout<<able[i][j];cout<<endl;
		}
	   */
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++)cin>>arr[i][j],arr[i][j] ^= 1;
	}
	INIT::GO();
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++)cout<<able[i][j];
		cout<<endl;
	}
	cin>>Q;
	while(Q--){
		int r,c;
		cin>>r>>c;
		QUERY::solve(r,c);
	}
	return 0;
}

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