Submission #399916

#	Time	Username	Problem	Language	Result	Execution time	Memory
399916		nikatamliani	Furniture (JOI20_furniture)	C++14	100 / 100	2223 ms	12872 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int cnt[N+N];
bool vis[N][N];
int n, m, q;
bool check_cell(int x, int y) {
	if(x == n && y == m) return false;
	if(x == 1 && y == 1) return false;
	if(x > 0 && y > 0 && x <= n && y <= m) {
		if((x == n || vis[x+1][y]) && (y == m || vis[x][y+1])) return true;
		if((x == 1 || vis[x-1][y]) && (y == 1 || vis[x][y-1])) return true;
	}
	return false;
}
void update(int x, int y) {
	if(vis[x][y]) return;
	vis[x][y] = 1;
	--cnt[x+y]; 
	for(int d = 0; d < 4; ++d) {
		int _x = x + dx[d];
		int _y = y + dy[d];
		if(check_cell(_x, _y)) {
			update(_x, _y);
		}
	}
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			++cnt[i+j];
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			int b; cin >> b;
			if(b) {
				update(i, j);
			}
		}
	}
	cin >> q;
	while(q--) {
		int x, y; cin >> x >> y;
		if(vis[x][y]) {
			cout << "1\n";
		} else {
			if(cnt[x+y] == 1) {
				cout << "0\n";
			} else {
				cout << "1\n";
				update(x, y);
			}
		}
	}
}

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