Submission #425006

#	Time	Username	Problem	Language	Result	Execution time	Memory
425006		p_square	Furniture (JOI20_furniture)	C++14	100 / 100	2498 ms	16900 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

bool avail[1005][1005][4];
bool C[1005][1005];
int maxn = 1005;

void block(int x, int y)
{
	//cout<<"Blocking "<<x<<" "<<y<<endl;
	if(C[x][y] == 1)
		return;
	C[x][y] = 1;

	avail[x][y+1][0] = 0;
	avail[x][y-1][2] = 0;
	avail[x+1][y][1] = 0;
	avail[x-1][y][3] = 0;

	if(avail[x][y][2])
	{
		if(!avail[x][y+1][1])
			block(x, y+1);
	}
	if(avail[x][y][3])
	{
		if(!avail[x+1][y][0])
			block(x+1, y);
	}
	if(avail[x][y][0])
	{
		if(!avail[x][y-1][3])
			block(x,y-1);
	}
	if(avail[x][y][1])
	{
		if(!avail[x-1][y][2])
			block(x-1, y);
	}
}

int main()
{
	int n, m, q;
	cin>>n>>m;
	for(int i = 0; i<maxn; i++)
	{
		for(int j = 0; j<maxn; j++)
		{
			for(int dir = 0; dir<4; dir++)
			{
				avail[i][j][dir] = 0;
			}
			C[i][j] = 1;
		}
	}

	for(int i = 1; i<=n; i++)
	{
		for(int j = 1; j<=m; j++)
		{
			if(i!=1)
				avail[i][j][1]=1;
			if(i!=n)
				avail[i][j][3]=1;
			if(j!=1)
				avail[i][j][0]=1;
			if(j!=m)
				avail[i][j][2]=1;

			C[i][j] = 0;
		}
	}

	int t;
	for(int i = 1; i<=n; i++)
	{
		for(int j = 1; j<=m; j++)
		{
			cin>>t;
			if(t)
				block(i,j);
		}
	}

	/*
	for(int i = 0; i<10; i++)
	{
		for(int j = 0; j<10; j++)
		{
			cout<<C[i][j]<<" ";
		}
		cout<<endl;
	}
	*/

	cin>>q;
	int x, y, js, ct;
	while(q--)
	{
		cin>>x>>y;
		if(C[x][y] == 1)
		{
			cout<<1<<endl;
			continue;
		}
		ct = 0;
		for(int i = 1; i<=n; i++)
		{
			js = x+y-i;
			if(js < 1 || js > m)
				continue;

			if(C[i][js]==0)
				ct++;
		}

		if(ct>1)
		{
			cout<<1<<endl;
			block(x,y);
		}
		else
		{
			cout<<0<<endl;
		}
	}

}

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