oj.uz

Submission #568060

# Submission time Handle Problem Language Result Execution time Memory
568060 2022-05-24T15:07:00 Z lovrot Furniture (JOI20_furniture) C++11
100 / 100
 855 ms 24164 KB 
#include <bits/stdc++.h> 
#include <unistd.h>

#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define vec vector
#define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov)
#define od(i, poc, n, pov) for(int i = (int) poc; i > (int) n; i -= (int) pov)

using namespace std;

const ll INF = 1e18;                              
const int LOG = 20;
const int OFF = (1 << LOG);
const int MOD = 1e9 + 7;
const int lx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int ly[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int N = 1010;
const int N2 = N + 10;

int abs(int x){ 
	if(x < 0)
		return -x;
	return x;
}

int n, m;
int h[N2 * N2], hi[N2][N2];
bool ban[N2][N2], west[N2 * N2], nrth[N2 * N2], mat[N2][N2];

int Find(int x){ 
	return (h[x] == x ? x : h[x] = Find(h[x]));
}

void Union(int x, int y){ 
	x = Find(x);
	y = Find(y);
	h[x] = y;
}

void update(int x, int y){ 
	if(ban[x][y])
		return;
	ban[x][y] = true;

	int hx = Find(hi[x][y]);

	if(!west[hx] && (x == n || y == 1))
		west[hx] = true;
	if(!nrth[hx] && (x == 1 || y == m))
		nrth[hx] = true;	

	pri(i, 0, 8, 1){ 
		if(!ban[x + lx[i]][y + ly[i]])
			continue;

		int h1 = Find(hi[x][y]);
		int h2 = Find(hi[x + lx[i]][y + ly[i]]);

		bool w = west[h1] | west[h2];
		bool nr = nrth[h1] | nrth[h2];

		Union(h2, h1);
		h1 = Find(h1);
		west[h1] = w;
		nrth[h1] = nr;
	}

	if(ban[x - 1][y + 1]){
		update(x, y + 1);
		update(x - 1, y);
	}
	if(ban[x + 1][y - 1]){
		update(x + 1, y);
		update(x, y - 1);
	}
}

bool can(int x, int y){ 
	bool can_n = (x == 1 || y == m);
	bool can_w = (x == n || y == 1);

	pri(i, 0, 8, 1){ 
		if(!ban[x + lx[i]][y + ly[i]])
			continue;

		int h1 = Find(hi[x + lx[i]][y + ly[i]]);
		can_n |= nrth[h1];
		can_w |= west[h1];
	}
	//cout << x << " " << y << " : " << can_w << " " << can_n << "\n";
	return !(can_w & can_n);
}

int main(){ 
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);

	pri(i, 0, N2, 1){ 
		pri(j, 0, N2, 1){
			hi[i][j] = i * N2 + j;
			h[i * N2 + j] = i * N2 + j; 
		}
	}

	cin >> n >> m;

	ban[0][0] = true;
	pri(i, 1, n + 1, 1){ 	
		ban[i][0] = true;
		ban[i][m + 1] = true;
		west[hi[i][0]] = true;
		nrth[hi[i][m + 1]] = true;

		pri(j, 1, m + 1, 1){ 
			ban[0][j] = true;
			ban[n + 1][j] = true;
			nrth[hi[0][j]] = true;
			west[hi[n + 1][j]] = true;

			cin >> mat[i][j];
		}
	}

	pri(i, 1, n + 1, 1){ 
		pri(j, 1, m + 1, 1){ 
			int x = mat[i][j];
			if(x){ 
				update(i, j);
			}
		}
	}

	int q; 
	cin >> q;

	pri(i, 0, q, 1){ 
		int x, y;
		cin >> x >> y;

		//pri(blax, 0, n + 2, 1) pri(blay, 0, m + 2, 1) cout << ban[blax][blay] << " \n"[blay == m + 1];

		bool res = can(x, y);
		cout << res << "\n";
		if(res)
			update(x, y);
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 8 ms 8868 KB Output is correct
3 Correct 8 ms 8836 KB Output is correct
4 Correct 9 ms 8864 KB Output is correct
5 Correct 9 ms 8916 KB Output is correct
6 Correct 10 ms 8916 KB Output is correct
7 Correct 9 ms 8992 KB Output is correct
8 Correct 9 ms 8916 KB Output is correct
9 Correct 9 ms 8916 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 8 ms 8868 KB Output is correct
3 Correct 8 ms 8836 KB Output is correct
4 Correct 9 ms 8864 KB Output is correct
5 Correct 9 ms 8916 KB Output is correct
6 Correct 10 ms 8916 KB Output is correct
7 Correct 9 ms 8992 KB Output is correct
8 Correct 9 ms 8916 KB Output is correct
9 Correct 9 ms 8916 KB Output is correct
10 Correct 23 ms 9036 KB Output is correct
11 Correct 8 ms 8736 KB Output is correct
12 Correct 450 ms 17220 KB Output is correct
13 Correct 108 ms 14228 KB Output is correct
14 Correct 729 ms 21772 KB Output is correct
15 Correct 769 ms 22032 KB Output is correct
16 Correct 791 ms 23008 KB Output is correct
17 Correct 855 ms 23688 KB Output is correct
18 Correct 694 ms 23204 KB Output is correct
19 Correct 739 ms 24040 KB Output is correct
20 Correct 539 ms 24072 KB Output is correct
21 Correct 686 ms 24164 KB Output is correct