Submission #335047

#	Time	Username	Problem	Language	Result	Execution time	Memory
335047		Mo_TOI_I_am_Garbage	Furniture (JOI20_furniture)	C++14	0 / 100	3 ms	1644 KiB

furniture

#include<bits/stdc++.h>
#define No_TOI_I_am_Garbage ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int arr[1050][1050], c[2][1050][1050], cnt[2050];
int main()
{
	No_TOI_I_am_Garbage
	int a, b; cin >> a >> b;
	for(int i=1; i <= a; i ++)
		for(int j=1; j <= b; j ++)
			cin >> arr[i][j];
	c[0][1][1] = c[1][a][b] = 1;
	for(int i=1; i <= a; i ++)
	{
		for(int j=1; j <= b; j ++)
		{
			if(arr[i][j]) continue;
			c[0][i][j] |= c[0][i - 1][j] | c[0][i][j - 1];
		}
	}
	for(int i=a; i >= 1; i --)
	{
		for(int j=b; j >= 1; j --)
		{
			if(arr[i][j]) continue;
			c[1][i][j] |= c[1][i + 1][j] | c[1][i][j + 1];
		}
	}
	for(int i=1; i <= a; i ++)
	{
		for(int j=1; j <= b; j ++)
		{
			arr[i][j] = c[0][i][j] & c[1][i][j];
			cnt[i + j] += arr[i][j];
		}
	}
	// for(int i=1; i <= a; i ++)
	// {
	// 	for(int j=1; j <= b; j ++)
	// 		cout << arr[i][j] << ' ';
	// 	cout << '\n';
	// }
	int q; cin >> q;
	for(int i=0; i < q; i ++)
	{
		int x, y; cin >> x >> y;
		if(cnt[x + y] - arr[x][y] == 0)
		{
			cout << 0 << '\n';
			continue;
		}
		cout << 1 << '\n';
		cnt[x + y] -= arr[x][y]; arr[x][y] = false;
		queue<pair<int, int> > Q;
		Q.push(make_pair(x, y));
		while(!Q.empty())
		{
			pair<int, int> top = Q.front(); Q.pop();
			int x = top.first, y = top.second;
			if(x + 1 <= a && arr[x + 1][y])
			{
				if(arr[x + 1][y - 1]) continue;
				arr[x + 1][y] = false;
				cnt[x + y + 1] --;
				Q.push(make_pair(x + 1, y));
			}
			if(y + 1 <= b && arr[x][y + 1])
			{
				if(arr[x - 1][y + 1]) continue;
				arr[x][y + 1] = false;
				cnt[x + y + 1] --;
				Q.push(make_pair(x, y + 1));
			}
			if(x - 1 >= a && arr[x - 1][y])
			{
				if(arr[x - 1][y + 1]) continue;
				arr[x - 1][y] = false;
				cnt[x + y - 1] --;
				Q.push(make_pair(x - 1, y));
			}
			if(y - 1 >= 1 && arr[x][y - 1])
			{
				if(arr[x + 1][y - 1]) continue;
				arr[x][y - 1] = false;
				cnt[x + y - 1] --;
				Q.push(make_pair(x, y - 1));
			}
		}
	}
	return 0;
}

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