제출 #869783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869783		serifefedartar	Furniture (JOI20_furniture)	C++17	100 / 100	180 ms	16632 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 30; 
const ll MAXN = 1100;

int path[MAXN][MAXN]; 
int cnt[2*MAXN], N, M;
void deactivate(int row, int col) {
	path[row][col] = 0;
	cnt[row+col]--; 

	if (row - 1 >= 1 && path[row-1][col] && path[row-1][col+1] == 0)
		deactivate(row-1, col);
	if (col - 1 >= 1 && path[row][col-1] && path[row+1][col-1] == 0)
		deactivate(row, col-1);
	if (row + 1 <= N && path[row+1][col] && path[row+1][col-1] == 0)
		deactivate(row+1, col);
	if (col + 1 <= M && path[row][col+1] && path[row-1][col+1] == 0)
		deactivate(row, col+1);
}

bool add(int row, int col) {
	if (cnt[row+col] == 1 && path[row][col])
		return false;
	if (path[row][col] == 0)
		return true; 
	deactivate(row, col);
	return true;
}

int main() {
	fast
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++)
			path[i][j] = true;
	}

	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 x; cin >> x;
			if (x)
				add(i, j);
		}
	}

	int Q;
	cin >> Q;
	while (Q--) {
		int row, col;
		cin >> row >> col;
		if (add(row, col))
			cout << "1\n";
		else
			cout << "0\n";
	}
}

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