Submission #411479

#	Time	Username	Problem	Language	Result	Execution time	Memory
411479		nichke	Furniture (JOI20_furniture)	C++14	0 / 100	6 ms	8624 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

int n, m, q;

int ar[1005][1005];
int val[1005][1005];
int cnt[2005];

bool change(int x, int y) {
	if (val[x][y] == 1) {
		return 1;
	}
	if (cnt[x + y] == 1) {
		return 0;
	}
	stack<pair<int, int>> st;
	if (val[x][y] == 0) {
		val[x][y] = 1;
		cnt[x + y]--;
		st.push({x, y});
	}
	while (!st.empty()) {
		int xx = st.top().first;
		int yy = st.top().second;
		st.pop();
		if (val[xx - 1][yy + 1] == 1) {
			if (val[xx - 1][yy] == 0) {
				val[xx - 1][yy] = 1;
				cnt[xx - 1 + yy]--;
				st.push({xx - 1, yy});
			}
			if (val[xx][yy + 1] == 0) {
				val[xx][yy + 1] = 1;
				cnt[xx + yy + 1]--;
				st.push({xx, yy + 1});
			}
		}
		if (val[xx + 1][yy - 1] == 1) {
			if (val[xx + 1][yy] == 0) {
				val[xx + 1][yy] = 1;
				cnt[xx + 1 + yy]--;
				st.push({xx + 1, yy});
			}
			if (val[xx][yy - 1] == 0) {
				val[xx][yy - 1] = 1;
				cnt[xx + yy - 1]--;
				st.push({xx, yy - 1});
			}
		}
	}
	return 1;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(val, 1, sizeof val);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> ar[i][j];
			val[i][j] = 0;
			cnt[i + j]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (ar[i][j] == 1) {
				change(i, j);
			}
		}
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x, y; cin >> x >> y;
		cout << change(x, y) << '\n';
	}
	return 0;
}

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