Submission #685730

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
685730	2023-01-24T22:38:56 Z	NK_	Furniture (JOI20_furniture)	C++17	100 / 100	278 ms	10792 KB

furniture

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;
	vector<vector<int>> A(N+2, vector<int>(M+2));
	vector<vector<int>> R(N+2, vector<int>(M+2, 1));

	for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) R[i][j] = 0;

	vector<int> C(N+M+1, 0);

	function<void(int, int)> fix = [&](int r, int c) {
		R[r][c] = 1;
		C[r+c]--;
		
		if (R[r+1][c-1] && !R[r+1][c]) fix(r+1, c);
		if (R[r+1][c-1] && !R[r][c-1]) fix(r, c-1);
		if (R[r-1][c+1] && !R[r-1][c]) fix(r-1, c);
		if (R[r-1][c+1] && !R[r][c+1]) fix(r, c+1);
	};

	for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) {
		cin >> A[i][j];
		C[i+j]++;

		if (A[i][j] && !R[i][j]) fix(i, j);
	}

	int Q; cin >> Q;
	for(int q = 0; q < Q; q++) {
		int r, c; cin >> r >> c;
		if (R[r][c]) cout << 1 << nl;
		else if (C[r+c] == 1) cout << 0 << nl;
		else {
			cout << 1 << nl;
			fix(r, c);
		}
	}



    return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	3 ms	468 KB	Output is correct
6	Correct	3 ms	468 KB	Output is correct
7	Correct	3 ms	468 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	3 ms	468 KB	Output is correct

Subtask #2

95.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	3 ms	468 KB	Output is correct
6	Correct	3 ms	468 KB	Output is correct
7	Correct	3 ms	468 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	3 ms	468 KB	Output is correct
10	Correct	11 ms	1092 KB	Output is correct
11	Correct	3 ms	468 KB	Output is correct
12	Correct	120 ms	8860 KB	Output is correct
13	Correct	57 ms	7848 KB	Output is correct
14	Correct	217 ms	9504 KB	Output is correct
15	Correct	271 ms	9172 KB	Output is correct
16	Correct	242 ms	9840 KB	Output is correct
17	Correct	266 ms	10356 KB	Output is correct
18	Correct	242 ms	10092 KB	Output is correct
19	Correct	278 ms	10728 KB	Output is correct
20	Correct	242 ms	10792 KB	Output is correct
21	Correct	264 ms	10656 KB	Output is correct