#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(234);
const ll inf = 1e18;
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("test", "r", stdin);
#endif
}
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m, 0));
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < m; j += 1) {
cin >> a[i][j];
}
}
vector<int> cnt_gd(n + m, 0);
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < m; j += 1) {
if (a[i][j] == 0) {
cnt_gd[i + j] += 1;
}
}
}
int qrs;
cin >> qrs;
vector<vector<pair<int, int>>> go2 = {{make_pair(0, 1), make_pair(0, -1)}, {make_pair(1, 0), make_pair(-1, 0)}};
auto is_ok = [&](int i, int j) {
return 0 <= i && i < n && 0 <= j && j < m;
};
auto is_bad = [&](int nx, int ny) {
if (nx == 0 && ny == 0) {
return false;
}
if (nx == n - 1 && ny == m - 1) {
return false;
}
for (auto dgo : go2) {
int cntbd = 0;
for (auto [dx, dy] : dgo) {
int nnx = nx + dx;
int nny = ny + dy;
if (!is_ok(nnx, nny)) {
cntbd += 1;
} else if (a[nnx][nny]) {
cntbd += 1;
}
}
if (cntbd >= 2) {
return true;
}
}
return false;
};
queue<pair<int, int>> q;
vector<pair<int, int>> go = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < m; j += 1) {
if (a[i][j]) {
continue;
}
if (is_bad(i, j)) {
q.push(make_pair(i, j));
}
}
};
auto serve_queue = [&] {
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if(a[x][y]){
continue;
}
cnt_gd[x + y] -= 1;
a[x][y] = 1;
for (auto [dx, dy] : go) {
int nx = x + dx;
int ny = y + dy;
if (!is_ok(nx, ny) || a[nx][ny]) {
continue;
}
if (is_bad(nx, ny)) {
q.push(make_pair(nx, ny));
}
}
}
};
serve_queue();
if (n >= 100 || m >= 100) {
// return 0;
}
vector<int> rs(qrs);
for (int itr = 0; itr < qrs; itr += 1) {
int x, y;
cin >> x >> y;
--x;
--y;
// rs[itr] = itr % 2;
// continue;
assert(cnt_gd[x + y] >= 1);
if (a[x][y]) {
rs[itr] = 1;
continue;
}
if (cnt_gd[x + y] == 1) {
rs[itr] = 0;
continue;
}
rs[itr] = 1;
q.push(make_pair(x, y));
serve_queue();
}
for (int i = 0; i < qrs; i += 1) {
cout << rs[i] << "\n";
}
return 0;
}
Compilation message
furniture.cpp: In lambda function:
furniture.cpp:53:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | for (auto [dx, dy] : dgo) {
| ^
furniture.cpp: In lambda function:
furniture.cpp:83:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
83 | auto [x, y] = q.front();
| ^
furniture.cpp:90:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
90 | for (auto [dx, dy] : go) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
