oj.uz

답안 #411479

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411479 2021-05-25T11:41:13 Z nichke Furniture (JOI20_furniture) C++14
0 / 100
 6 ms 8624 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

int n, m, q;

int ar[1005][1005];
int val[1005][1005];
int cnt[2005];

bool change(int x, int y) {
	if (val[x][y] == 1) {
		return 1;
	}
	if (cnt[x + y] == 1) {
		return 0;
	}
	stack<pair<int, int>> st;
	if (val[x][y] == 0) {
		val[x][y] = 1;
		cnt[x + y]--;
		st.push({x, y});
	}
	while (!st.empty()) {
		int xx = st.top().first;
		int yy = st.top().second;
		st.pop();
		if (val[xx - 1][yy + 1] == 1) {
			if (val[xx - 1][yy] == 0) {
				val[xx - 1][yy] = 1;
				cnt[xx - 1 + yy]--;
				st.push({xx - 1, yy});
			}
			if (val[xx][yy + 1] == 0) {
				val[xx][yy + 1] = 1;
				cnt[xx + yy + 1]--;
				st.push({xx, yy + 1});
			}
		}
		if (val[xx + 1][yy - 1] == 1) {
			if (val[xx + 1][yy] == 0) {
				val[xx + 1][yy] = 1;
				cnt[xx + 1 + yy]--;
				st.push({xx + 1, yy});
			}
			if (val[xx][yy - 1] == 0) {
				val[xx][yy - 1] = 1;
				cnt[xx + yy - 1]--;
				st.push({xx, yy - 1});
			}
		}
	}
	return 1;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(val, 1, sizeof val);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> ar[i][j];
			val[i][j] = 0;
			cnt[i + j]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (ar[i][j] == 1) {
				change(i, j);
			}
		}
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x, y; cin >> x >> y;
		cout << change(x, y) << '\n';
	}
	return 0;
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8524 KB Output is correct
2 Incorrect 6 ms 8624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8524 KB Output is correct
2 Incorrect 6 ms 8624 KB Output isn't correct
3 Halted 0 ms 0 KB -