oj.uz

Submission #335048

# Submission time Handle Problem Language Result Execution time Memory
335048 2020-12-11T01:10:36 Z Mo_TOI_I_am_Garbage Furniture (JOI20_furniture) C++14
100 / 100
 3092 ms 24672 KB 
#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];
		}
	}
	int q; cin >> q;
	for(int i=0; i < q; i ++)
	{
		// for(int j=1; j <= a; j ++)
		// {
		// 	for(int k=1; k <= b; k ++)
		// 		cout << arr[j][k] << ' ';
		// 	cout << '\n';
		// }
		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] && !arr[x + 1][y - 1])
			{
				arr[x + 1][y] = false;
				cnt[x + y + 1] --;
				Q.push(make_pair(x + 1, y));
			}
			if(y + 1 <= b && arr[x][y + 1] && !arr[x - 1][y + 1])
			{
				arr[x][y + 1] = false;
				cnt[x + y + 1] --;
				Q.push(make_pair(x, y + 1));
			}
			if(x - 1 >= 1 && arr[x - 1][y] && !arr[x - 1][y + 1])
			{
				arr[x - 1][y] = false;
				cnt[x + y - 1] --;
				Q.push(make_pair(x - 1, y));
			}
			if(y - 1 >= 1 && arr[x][y - 1] && !arr[x + 1][y - 1])
			{
				arr[x][y - 1] = false;
				cnt[x + y - 1] --;
				Q.push(make_pair(x, y - 1));
			}
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 11 ms 1516 KB Output is correct
3 Correct 13 ms 1516 KB Output is correct
4 Correct 23 ms 1664 KB Output is correct
5 Correct 26 ms 1644 KB Output is correct
6 Correct 32 ms 1744 KB Output is correct
7 Correct 30 ms 1644 KB Output is correct
8 Correct 31 ms 1644 KB Output is correct
9 Correct 31 ms 1644 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 11 ms 1516 KB Output is correct
3 Correct 13 ms 1516 KB Output is correct
4 Correct 23 ms 1664 KB Output is correct
5 Correct 26 ms 1644 KB Output is correct
6 Correct 32 ms 1744 KB Output is correct
7 Correct 30 ms 1644 KB Output is correct
8 Correct 31 ms 1644 KB Output is correct
9 Correct 31 ms 1644 KB Output is correct
10 Correct 74 ms 1388 KB Output is correct
11 Correct 18 ms 1004 KB Output is correct
12 Correct 1022 ms 17428 KB Output is correct
13 Correct 195 ms 14060 KB Output is correct
14 Correct 2532 ms 21896 KB Output is correct
15 Correct 2654 ms 21988 KB Output is correct
16 Correct 2900 ms 22892 KB Output is correct
17 Correct 3011 ms 24052 KB Output is correct
18 Correct 2917 ms 23404 KB Output is correct
19 Correct 3073 ms 24652 KB Output is correct
20 Correct 2997 ms 24332 KB Output is correct
21 Correct 3092 ms 24672 KB Output is correct