Submission #685730

#	Time	Username	Problem	Language	Result	Execution time	Memory
685730		NK_	Furniture (JOI20_furniture)	C++17	100 / 100	278 ms	10792 KiB

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 / 5
• Subtask 2: 95 / 95