oj.uz

Submission #807874

# Submission time Handle Problem Language Result Execution time Memory
807874 2023-08-05T03:37:52 Z rxlfd314 Furniture (JOI20_furniture) C++17
100 / 100
 259 ms 12080 KB 
#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));
	vector<int> dcnt(N+M+1, 0);
	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-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+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++) {
			bool b;
			cin >> b;
			if (b) {
				yeet(i, j);
			}
		}
	}
	
	int Q;
	for (cin >> Q; Q--; ) {
		int i, j;
		cin >> i >> j;
		if (bad[i][j] || dcnt[i+j] < min(N, i+j-1) - max(1, i+j-M)) {
			yeet(i, j);
			cout << "1\n";
		} else {
			cout << "0\n";
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 372 KB Output is correct
8 Correct 3 ms 428 KB Output is correct
9 Correct 3 ms 340 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 372 KB Output is correct
8 Correct 3 ms 428 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 124 ms 5068 KB Output is correct
13 Correct 53 ms 2184 KB Output is correct
14 Correct 204 ms 9908 KB Output is correct
15 Correct 212 ms 10192 KB Output is correct
16 Correct 224 ms 11096 KB Output is correct
17 Correct 226 ms 11672 KB Output is correct
18 Correct 240 ms 11352 KB Output is correct
19 Correct 259 ms 11980 KB Output is correct
20 Correct 227 ms 12080 KB Output is correct
21 Correct 238 ms 12004 KB Output is correct