Submission #583180

#	Time	Username	Problem	Language	Result	Execution time	Memory
583180		penguinhacker	Furniture (JOI20_furniture)	C++17	0 / 100	13 ms	1100 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1000, dx[8]={-1, -1, -1, 0, 0, 1, 1, 1}, dy[8]={-1, 0, 1, -1, 1, -1, 0, 1};
int n, m, q, c[mxN][mxN], p[mxN*mxN+2];
set<int> row[mxN], col[mxN];

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

int find(int i, int j) {
	return find(i*m+j);
}

void mrg(int u, int v) {
	if (u<v)
		swap(u, v);
	p[v]=u;
}

vector<ar<int, 2>> get_adj(int i, int j) {
	vector<ar<int, 2>> v;
	for (int k=0; k<8; ++k) {
		int ni=i+dx[k], nj=j+dy[k];
		if (0<=ni&&ni<n&&0<=nj&&nj<m&&c[ni][nj])
			v.push_back({ni, nj});
	}
	return v;
}

bool bad(int i, int j) {
	bool leftdown=i==n-1||j==0, upright=i==0||j==m-1;
	for (auto [x, y] : get_adj(i, j)) {
		//cout << i << " " << j << " " << x << " " << y << endl;
		leftdown|=find(x, y)==n*m;
		upright|=find(x, y)==n*m+1;
	}
	return leftdown&&upright;
}

void add(int i, int j) {
	if (i==n-1||j==0)
		mrg(find(i, j), n*m);
	if (i==0||j==m-1)
		mrg(find(i, j), n*m+1);
	for (auto [x, y] : get_adj(i, j))
		mrg(find(i, j), find(x, y));
	c[i][j]=1;
	row[i].insert(j);
	col[j].insert(i);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	iota(p, p+n*m+2, 0);
	for (int i=0; i<n; ++i)
		for (int j=0; j<m; ++j) {
			cin >> c[i][j];
			if (c[i][j])
				add(i, j);
		}
	cin >> q;
	while(q--) {
		int i, j;
		cin >> i >> j, --i, --j;
		assert(!c[i][j]);
		if (bad(i, j)) {
			cout << "0\n";
			continue;
		}
		c[i][j]=1;
		row[i].insert(j);
		col[j].insert(i);
		int last=-1;
		bool ok=1;
		for (int i=0; i<n; ++i) {
			if (row[i].empty()||*row[i].rbegin()<last-1) {
				ok=0;
				break;
			}
			last=*row[i].lower_bound(last-1);
			while(last&&c[i][last-1])
				--last;
			if (!last)
				break;
		}
		if (ok) {
			c[i][j]=0;
			row[i].erase(j);
			col[j].erase(i);
			cout << "0\n";
			continue;
		}
		last=-1, ok=1;
		for (int i=0; i<m; ++i) {
			if (col[i].empty()||*col[i].rbegin()<last-1) {
				ok=0;
				break;
			}
			last=*col[i].lower_bound(last-1);
			while(last&&c[last-1][i])
				--last;
			if (!last)
				break;
		}
		if (ok) {
			c[i][j]=0;
			row[i].erase(j);
			col[j].erase(i);
			cout << "0\n";
			continue;
		}
		cout << "1\n";
		add(i, j);
	}
	return 0;
}

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