Submission #568060

#	Time	Username	Problem	Language	Result	Execution time	Memory
568060		lovrot	Furniture (JOI20_furniture)	C++11	100 / 100	855 ms	24164 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95