Submission #961769

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
961769	2024-04-12T12:20:28 Z	pcc	Furniture (JOI20_furniture)	C++17	100 / 100	506 ms	63512 KB

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++)cerr<<able[i][j];cerr<<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++)cerr<<able[i][j];
		cerr<<endl;
	}

   */
	cin>>Q;
	while(Q--){
		int r,c;
		cin>>r>>c;
		QUERY::solve(r,c);
	}
	return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	2 ms	4700 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4952 KB	Output is correct
5	Correct	3 ms	5164 KB	Output is correct
6	Correct	4 ms	5328 KB	Output is correct
7	Correct	4 ms	5212 KB	Output is correct
8	Correct	4 ms	5212 KB	Output is correct
9	Correct	4 ms	5212 KB	Output is correct

Subtask #2

95.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	2 ms	4700 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4952 KB	Output is correct
5	Correct	3 ms	5164 KB	Output is correct
6	Correct	4 ms	5328 KB	Output is correct
7	Correct	4 ms	5212 KB	Output is correct
8	Correct	4 ms	5212 KB	Output is correct
9	Correct	4 ms	5212 KB	Output is correct
10	Correct	6 ms	4956 KB	Output is correct
11	Correct	5 ms	4956 KB	Output is correct
12	Correct	440 ms	45276 KB	Output is correct
13	Correct	172 ms	31992 KB	Output is correct
14	Correct	503 ms	49264 KB	Output is correct
15	Correct	498 ms	54320 KB	Output is correct
16	Correct	368 ms	58564 KB	Output is correct
17	Correct	403 ms	61348 KB	Output is correct
18	Correct	506 ms	60292 KB	Output is correct
19	Correct	407 ms	63512 KB	Output is correct
20	Correct	378 ms	63476 KB	Output is correct
21	Correct	452 ms	63312 KB	Output is correct