oj.uz

Submission #421292

# Submission time Handle Problem Language Result Execution time Memory
421292 2021-06-09T01:10:07 Z Marceantasy Furniture (JOI20_furniture) C++17
100 / 100
 412 ms 12948 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 1 ms 336 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 412 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 412 KB Output is correct
10 Correct 15 ms 744 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 200 ms 4076 KB Output is correct
13 Correct 112 ms 3272 KB Output is correct
14 Correct 353 ms 5020 KB Output is correct
15 Correct 383 ms 5076 KB Output is correct
16 Correct 350 ms 5700 KB Output is correct
17 Correct 376 ms 12552 KB Output is correct
18 Correct 381 ms 12224 KB Output is correct
19 Correct 388 ms 12948 KB Output is correct
20 Correct 396 ms 12892 KB Output is correct
21 Correct 412 ms 12944 KB Output is correct