oj.uz

Submission #399917

# Submission time Handle Problem Language Result Execution time Memory
399917 2021-05-06T22:54:59 Z nikatamliani Furniture (JOI20_furniture) C++14
100 / 100
 310 ms 3276 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() {
	ios::sync_with_stdio(0); cin.tie(0);
	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) {
			bool 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 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 11 ms 424 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 174 ms 1876 KB Output is correct
13 Correct 85 ms 1288 KB Output is correct
14 Correct 287 ms 2812 KB Output is correct
15 Correct 273 ms 2920 KB Output is correct
16 Correct 277 ms 3064 KB Output is correct
17 Correct 286 ms 3252 KB Output is correct
18 Correct 292 ms 3140 KB Output is correct
19 Correct 307 ms 3272 KB Output is correct
20 Correct 303 ms 3264 KB Output is correct
21 Correct 310 ms 3276 KB Output is correct