Submission #807166

#	Time	Username	Problem	Language	Result	Execution time	Memory
807166		rxlfd314	Furniture (JOI20_furniture)	C++17	0 / 100	1 ms	340 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N, M;
	cin >> N >> M;
	vector<vector<bool>> bad(N+2, vector<bool>(M+2, 0));
	int dcnt[N+M+1] = {};
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			bool b;
			cin >> b;
			bad[i][j] = b;
			dcnt[i+j] += bad[i][j];
		}
	}
	for (int i = 0; i < N+2; i++) {
		bad[i][0] = bad[i][M+1] = 1;
	}
	for (int i = 0; i < M+2; i++) {
		bad[0][i] = bad[N+1][i] = 1;
	}
	
	auto yeet = [&](int X, int Y) {
		queue<ari2> qu;
		qu.push({X, Y});
		dcnt[X+Y] += !bad[X][Y];
		bad[X][Y] = 1;
		while (qu.size()) {
			auto [i, j] = qu.front();
			qu.pop();
			if (bad[i][j] && bad[i-1][j+1]) {
				if (!bad[i-1][j]) {
					qu.push({i-1, j});
					dcnt[i-1+j]++;
				}
				if (!bad[i][j+1]) {
					qu.push({i, j+1});
					dcnt[i+j+1]++;
				}
				bad[i-1][j] = bad[i][j+1] = 1;
			}
			if (bad[i][j] && bad[i+1][j-1]) {
				if (!bad[i][j-1]) {
					qu.push({i, j-1});
					dcnt[i+j-1]++;
				}
				if (!bad[i+1][j]) {
					qu.push({i+1, j});
					dcnt[i+1+j]++;
				}
				bad[i][j-1] = bad[i+1][j] = 1;
			}
		}
	};
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (!bad[i][j]) continue;
			yeet(i, j);
		}
	}
	
	for (int i = 2; i <= N+M; i++) {
		cout << dcnt[i] << "\n "[i<N+M];
	}
	
	int Q;
	for (cin >> Q; Q--; ) {
		int i, j;
		cin >> i >> j;
		if (bad[i][j] || dcnt[i+j] < min(N, i+j) - max(1, i+j-M)) {
			yeet(i, j);
			cout << "1\n";
		} else {
			cout << "0\n";
		}
	}
}

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