Submission #422728

#	Time	Username	Problem	Language	Result	Execution time	Memory
422728		Jasiekstrz	Furniture (JOI20_furniture)	C++17	100 / 100	428 ms	20924 KiB

furniture

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
vector<pair<int,int>> moves[2]={{{1,0},{0,1}},{{-1,0},{0,-1}}};
bool tab[N+10][N+10];
int ways[N+10][N+10][2];
int cnt[3*N+10];
void del(int x,int y,bool t)
{
	if(ways[x][y][t]==0)
		return;
	ways[x][y][t]=0;
	if(ways[x][y][!t]>0)
		cnt[x+y]--;
	for(auto mv:moves[t])
	{
		int vx=x+mv.fi,vy=y+mv.se;
		if(ways[vx][vy][t]==0)
			continue;
		if(ways[vx][vy][t]==1)
			del(vx,vy,t);
		else
			ways[vx][vy][t]--;
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cnt[i+j]++;
			ways[i][j][0]=ways[i][j][1]=2;
			if(i==1 || j==1)
				ways[i][j][0]=1;
			if(i==n || j==m)
				ways[i][j][1]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>tab[i][j];
			if(tab[i][j])
			{
				del(i,j,0);
				del(i,j,1);
			}
		}
	}
	//for(int i=2;i<=n+m;i++)
	//	cerr<<"i+j="<<i<<" -> "<<cnt[i]<<"\n";
	//for(int i=1;i<=n;i++)
	//{
	//	for(int j=1;j<=m;j++)
	//		cerr<<"("<<ways[i][j][0]<<","<<ways[i][j][1]<<")"<<" \n"[j==m];
	//}
	int q;
	cin>>q;
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(cnt[a+b]>1 || ways[a][b][0]==0 || ways[a][b][1]==0)
		{
			cout<<"1\n";
			if(ways[a][b][0]>0)
				del(a,b,0);
			if(ways[a][b][1]>0)
				del(a,b,1);
		}
		else
			cout<<"0\n";
	}
	return 0;
}

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