#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
bool a[N][N], b[N][N];
int n, m, q, x[N], y[N], cnt[N][N];
bool check(int id, int banned_x = 0, int banned_y = 0) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
b[i][j] = a[i][j];
cnt[i][j] = 0;
}
}
for(int i = 1; i <= id; ++i) {
b[x[i]][y[i]] = 1;
}
b[banned_x][banned_y] = 0;
cnt[1][1] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(b[i][j] == 0) {
cnt[i][j] += cnt[i-1][j];
cnt[i][j] += cnt[i][j-1];
cnt[i][j] = min(cnt[i][j], 2);
}
}
}
if(banned_x == 0)
return cnt[n][m] == 0;
return cnt[n][m] < 2;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
cin >> q;
for(int i = 1; i <= q; ++i) {
cin >> x[i] >> y[i];
}
int l = 1, r = q, pos1 = q+1, pos2 = q+1;
while(r >= l) {
int m = l + r >> 1;
if(check(m)) {
r = m - 1;
pos1 = m;
} else {
l = m + 1;
}
}
l = pos1, r = q;
while(r >= l) {
int m = l + r >> 1;
if(check(m, x[pos1], y[pos1])) {
r = m - 1;
pos2 = m;
} else {
l = m + 1;
}
}
check(pos2, x[pos1], y[pos1]);
for(int i = 1; i <= q; ++i) {
if(i < pos1) {
cout << "1\n";
} else if(i < pos2) {
if(x[i] == x[pos1] && y[i] == y[pos1]) {
cout << "0\n";
} else {
cout << "1\n";
}
} else {
cout << (cnt[x[i]][y[i]] != 1) << '\n';
}
}
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int m = l + r >> 1;
| ~~^~~
furniture.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
708 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
708 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
