Submission #313707

#	Time	Username	Problem	Language	Result	Execution time	Memory
313707		Temmie	Furniture (JOI20_furniture)	C++17	0 / 100	2 ms	640 KiB

furniture

#include <bits/stdc++.h>

void place(int X, int Y, std::queue <std::pair <int, int>>& q, std::vector <int>& le, std::vector <int>& ri, std::vector <std::vector <int>>& g, std::vector <std::vector <int>>& ou, std::vector <std::vector <int>>& in, int n, int m) {
	q.push({ X, Y });
	while (q.size()) {
		auto p = q.front(); q.pop();
		int x = p.first, y = p.second;
		if (g[x][y]) continue;
		g[x][y] = 1;
		if (x && !--ou[x - 1][y]) q.push({ x - 1, y });
		if (y && !--ou[x][y - 1]) q.push({ x, y - 1 });
		if (x + 2 <= n && !--in[x + 1][y]) q.push({ x + 1, y });
		if (y + 2 <= m && !--in[x][y + 1]) q.push({ x, y + 2 });
		while (le[x + y] == x && g[x][y]) le[x + y]++, x++, y--;
		while (ri[x + y] == x && g[x][y]) ri[x + y]--, x--, y++;
	}
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	int n, m; std::cin >> n >> m;
	std::vector <std::vector <int>> g(n, std::vector <int> (m)), ou(g), in(g);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (j + 2 <= m) ou[i][j]++, in[i][j + 1]++;
			if (i + 2 <= n) ou[i][j]++, in[i + 1][j]++;
		}
	}
	std::vector <int> le(n + m, n), ri(n + m, 0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			le[i + j] = std::min(le[i + j], i);
			ri[i + j] = std::max(ri[i + j], i);
		}
	}
	std::queue <std::pair <int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int p; std::cin >> p;
			if (p) place(i, j, q, le, ri, g, ou, in, n, m);
		}
	}
	int k; std::cin >> k;
	while (k--) {
		int x, y; std::cin >> x >> y; x--, y--;
		if (le[x + y] == x && ri[x + y] == x) {
			std::cout << "0\n"; continue;
		}
		std::cout << "1\n";
		place(x, y, q, le, ri, g, ou, in, n, m);
	}
	
}















































































// :D

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