oj.uz

Submission #399916

# Submission time Handle Problem Language Result Execution time Memory
399916 2021-05-06T22:53:16 Z nikatamliani Furniture (JOI20_furniture) C++14
100 / 100
 2223 ms 12872 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int cnt[N+N];
bool vis[N][N];
int n, m, q;
bool check_cell(int x, int y) {
	if(x == n && y == m) return false;
	if(x == 1 && y == 1) return false;
	if(x > 0 && y > 0 && x <= n && y <= m) {
		if((x == n || vis[x+1][y]) && (y == m || vis[x][y+1])) return true;
		if((x == 1 || vis[x-1][y]) && (y == 1 || vis[x][y-1])) return true;
	}
	return false;
}
void update(int x, int y) {
	if(vis[x][y]) return;
	vis[x][y] = 1;
	--cnt[x+y]; 
	for(int d = 0; d < 4; ++d) {
		int _x = x + dx[d];
		int _y = y + dy[d];
		if(check_cell(_x, _y)) {
			update(_x, _y);
		}
	}
}
int main() {
	cin >> n >> m;
	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 b; cin >> b;
			if(b) {
				update(i, j);
			}
		}
	}
	cin >> q;
	while(q--) {
		int x, y; cin >> x >> y;
		if(vis[x][y]) {
			cout << "1\n";
		} else {
			if(cnt[x+y] == 1) {
				cout << "0\n";
			} else {
				cout << "1\n";
				update(x, y);
			}
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 10 ms 440 KB Output is correct
4 Correct 20 ms 476 KB Output is correct
5 Correct 20 ms 464 KB Output is correct
6 Correct 23 ms 460 KB Output is correct
7 Correct 22 ms 496 KB Output is correct
8 Correct 22 ms 460 KB Output is correct
9 Correct 22 ms 500 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 10 ms 440 KB Output is correct
4 Correct 20 ms 476 KB Output is correct
5 Correct 20 ms 464 KB Output is correct
6 Correct 23 ms 460 KB Output is correct
7 Correct 22 ms 496 KB Output is correct
8 Correct 22 ms 460 KB Output is correct
9 Correct 22 ms 500 KB Output is correct
10 Correct 58 ms 644 KB Output is correct
11 Correct 14 ms 332 KB Output is correct
12 Correct 764 ms 5912 KB Output is correct
13 Correct 184 ms 3048 KB Output is correct
14 Correct 1808 ms 10688 KB Output is correct
15 Correct 1881 ms 11032 KB Output is correct
16 Correct 2090 ms 11876 KB Output is correct
17 Correct 2152 ms 12436 KB Output is correct
18 Correct 2130 ms 12176 KB Output is correct
19 Correct 2223 ms 12864 KB Output is correct
20 Correct 2206 ms 12868 KB Output is correct
21 Correct 2180 ms 12872 KB Output is correct