Submission #636839

#	Time	Username	Problem	Language	Result	Execution time	Memory
636839		valerikk	Furniture (JOI20_furniture)	C++17	100 / 100	286 ms	17796 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, m;
int a[N][N];
bool dp1[N][N], dp2[N][N];
int cnt[2 * N];

bool get1(int i, int j) {
	if (a[i][j]) return false;
	if (i == 0 && j == 0) return true;
	if (i > 0 && dp1[i - 1][j]) return true;
	if (j > 0 && dp1[i][j - 1]) return true;
	return false; 
}

bool get2(int i, int j) {
	if (a[i][j]) return false;
	if (i == n - 1 && j == m - 1) return true;
	if (i < n - 1 && dp2[i + 1][j]) return true;
	if (j < m - 1 && dp2[i][j + 1]) return true;
	return false;
}

void del1(int i, int j) {
	if (!dp1[i][j]) return;
	if (dp2[i][j]) --cnt[i + j];
	dp1[i][j] = false;
	if (i + 1 < n && !get1(i + 1, j)) del1(i + 1, j);
	if (j + 1 < m && !get1(i, j + 1)) del1(i, j + 1);
}

void del2(int i, int j) {
	if (!dp2[i][j]) return;
	if (dp1[i][j]) --cnt[i + j];
	dp2[i][j] = false;
	if (i > 0 && !get2(i - 1, j)) del2(i - 1, j);
	if (j > 0 && !get2(i, j - 1)) del2(i, j - 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			dp1[i][j] = get1(i, j);
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		for (int j = m - 1; j >= 0; --j) {
			dp2[i][j] = get2(i, j);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (dp1[i][j] && dp2[i][j]) {
				++cnt[i + j];
			}
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		if (!dp1[x][y] || !dp2[x][y] || cnt[x + y] >= 2) {
			cout << "1\n";
			a[x][y] = 1;
			del1(x, y);
			del2(x, y);
		} else {
			cout << "0\n";
		}
	}
	return 0;
}

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