oj.uz

Submission #636839

# Submission time Handle Problem Language Result Execution time Memory
636839 2022-08-30T10:01:11 Z valerikk Furniture (JOI20_furniture) C++17
100 / 100
 286 ms 17796 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, m;
int a[N][N];
bool dp1[N][N], dp2[N][N];
int cnt[2 * N];

bool get1(int i, int j) {
	if (a[i][j]) return false;
	if (i == 0 && j == 0) return true;
	if (i > 0 && dp1[i - 1][j]) return true;
	if (j > 0 && dp1[i][j - 1]) return true;
	return false; 
}

bool get2(int i, int j) {
	if (a[i][j]) return false;
	if (i == n - 1 && j == m - 1) return true;
	if (i < n - 1 && dp2[i + 1][j]) return true;
	if (j < m - 1 && dp2[i][j + 1]) return true;
	return false;
}

void del1(int i, int j) {
	if (!dp1[i][j]) return;
	if (dp2[i][j]) --cnt[i + j];
	dp1[i][j] = false;
	if (i + 1 < n && !get1(i + 1, j)) del1(i + 1, j);
	if (j + 1 < m && !get1(i, j + 1)) del1(i, j + 1);
}

void del2(int i, int j) {
	if (!dp2[i][j]) return;
	if (dp1[i][j]) --cnt[i + j];
	dp2[i][j] = false;
	if (i > 0 && !get2(i - 1, j)) del2(i - 1, j);
	if (j > 0 && !get2(i, j - 1)) del2(i, j - 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			dp1[i][j] = get1(i, j);
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		for (int j = m - 1; j >= 0; --j) {
			dp2[i][j] = get2(i, j);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (dp1[i][j] && dp2[i][j]) {
				++cnt[i + j];
			}
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		if (!dp1[x][y] || !dp2[x][y] || cnt[x + y] >= 2) {
			cout << "1\n";
			a[x][y] = 1;
			del1(x, y);
			del2(x, y);
		} else {
			cout << "0\n";
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 932 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 5 ms 980 KB Output is correct
9 Correct 5 ms 980 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 932 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 5 ms 980 KB Output is correct
9 Correct 5 ms 980 KB Output is correct
10 Correct 8 ms 980 KB Output is correct
11 Correct 3 ms 600 KB Output is correct
12 Correct 153 ms 10732 KB Output is correct
13 Correct 53 ms 7684 KB Output is correct
14 Correct 285 ms 15344 KB Output is correct
15 Correct 236 ms 15628 KB Output is correct
16 Correct 259 ms 16572 KB Output is correct
17 Correct 278 ms 17356 KB Output is correct
18 Correct 238 ms 16844 KB Output is correct
19 Correct 286 ms 17744 KB Output is correct
20 Correct 232 ms 17796 KB Output is correct
21 Correct 253 ms 17740 KB Output is correct