// #pragma gcc optimize("O3,unroll-loops")
// #pragma gcc target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)v.size()
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;
const int N = 1e3 + 2;
namespace UR {
int n, m;
bool vis[N][N], on_path[N][N];
vector<ii> path, extended_path;
void set_nm(int x, int y) {
// swap(x, y);
n = x, m = y;
}
void set_cell(int x, int y, int value) {
// swap(x, y);
vis[x][y] = value;
}
bool get_on_path(int x, int y) {
// swap(x, y);
return on_path[x][y];
}
ii prv(int x, int y) {
if(on_path[x-1][y]) return {x-1, y};
if(on_path[x][y-1]) return {x, y-1};
assert(false);
}
int nxt(int x, int y) {
if(on_path[x+1][y]) return 2;
if(on_path[x][y+1]) return 1;
assert(false);
}
int dfs(int x, int y) {
// cerr << "dfs " << x << ' ' << y << endl;
if(x > n or y > m) return 0;
if(x == n and y == m) {
on_path[x][y] = 1;
extended_path.emplace_back(n, m);
return 1;
}
if(!vis[x][y+1]) {
int ret = dfs(x, y+1);
if(ret) {
on_path[x][y] = 1;
extended_path.emplace_back(x, y);
return 1;
}
}
if(!vis[x+1][y]) {
int ret = dfs(x+1, y);
if(ret) {
on_path[x][y] = 1;
extended_path.emplace_back(x, y);
return 1;
}
}
vis[x][y] = 1;
return 0;
}
void update(int x, int y) {
vis[x][y] = 1;
bool flag = 0;
int p, q;
tie(p, q) = ii(x, y);
int cnt = 10;
while(p != 1 or q != 1) {
tie(p, q) = prv(p, q);
if(nxt(p, q) == 2) {
continue;
}
int pp = p+1, qq = q;
if(!vis[pp][qq] and dfs(pp, qq)) {
while(path.back() != ii(p, q)) {
ii pa = path.back();
on_path[pa.fi][pa.se] = 0;
// vis[pa.fi][pa.se] = 1; // CHECK THIS!
path.pop_back();
}
while(extended_path.size()) {
ii pa = extended_path.back();
path.push_back(pa);
on_path[pa.fi][pa.se] = 1;
extended_path.pop_back();
}
flag = true;
break;
}
}
assert(flag);
}
void init() {
dfs(1, 1);
path = extended_path;
reverse(all(path));
extended_path.clear();
}
void destroy(int x, int y) {
// swap(x, y);
if(!on_path[x][y]) {
vis[x][y] = 1;
return;
}
update(x, y);
}
}
namespace LL {
int n, m;
bool vis[N][N], on_path[N][N];
vector<ii> path, extended_path;
void set_nm(int x, int y) {
swap(x, y);
n = x, m = y;
}
void set_cell(int x, int y, int value) {
swap(x, y);
vis[x][y] = value;
}
bool get_on_path(int x, int y) {
swap(x, y);
return on_path[x][y];
}
ii prv(int x, int y) {
if(on_path[x-1][y]) return {x-1, y};
if(on_path[x][y-1]) return {x, y-1};
assert(false);
}
int nxt(int x, int y) {
if(on_path[x+1][y]) return 2;
if(on_path[x][y+1]) return 1;
assert(false);
}
int dfs(int x, int y) {
// cerr << "dfs> " << x << ' ' << y << endl;
if(x > n or y > m) return 0;
if(x == n and y == m) {
on_path[x][y] = 1;
extended_path.emplace_back(n, m);
return 1;
}
if(!vis[x][y+1]) {
int ret = dfs(x, y+1);
if(ret) {
on_path[x][y] = 1;
extended_path.emplace_back(x, y);
return 1;
}
}
if(!vis[x+1][y]) {
int ret = dfs(x+1, y);
if(ret) {
on_path[x][y] = 1;
extended_path.emplace_back(x, y);
return 1;
}
}
vis[x][y] = 1;
return 0;
}
void update(int x, int y) {
vis[x][y] = 1;
bool flag = 0;
int p, q;
tie(p, q) = ii(x, y);
int cnt = 10;
while(p != 1 or q != 1) {
tie(p, q) = prv(p, q);
if(nxt(p, q) == 2) {
continue;
}
int pp = p+1, qq = q;
if(!vis[pp][qq] and dfs(pp, qq)) {
while(path.back() != ii(p, q)) {
ii pa = path.back();
on_path[pa.fi][pa.se] = 0;
// vis[pa.fi][pa.se] = 1; // CHECK THIS!
path.pop_back();
}
while(extended_path.size()) {
ii pa = extended_path.back();
path.push_back(pa);
on_path[pa.fi][pa.se] = 1;
extended_path.pop_back();
}
flag = true;
break;
}
}
/*if(!flag) {
cerr << x << ' ' << y << endl;
}*/
assert(flag);
}
void init() {
dfs(1, 1);
path = extended_path;
reverse(all(path));
extended_path.clear();
}
void destroy(int x, int y) {
swap(x, y);
if(!on_path[x][y]) {
vis[x][y] = 1;
return;
}
update(x, y);
}
}
// int n, m, g[N][N];
char out[2 * N * N];
int ptr = 0;
// bool on_path[N][N];
// int vis[N][N];
// vector<ii> extended_path, path;
int n, m;
template<typename T>
void print_arr(T arr[N][N]) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cerr << arr[i][j];
} cerr << endl;
}
}
/*ii prv(int x, int y) {
if(on_path[x-1][y]) return {x-1, y};
if(on_path[x][y-1]) return {x, y-1};
// cerr << x << ' ' << y << endl;
assert(false);
}
int nxt(int x, int y) {
if(on_path[x+1][y]) return 2;
if(on_path[x][y+1]) return 1;
assert(false);
}
int dfs(int x, int y) {
// cerr << "dfs " << x << ' ' << y << endl;
if(x == n and y == m) {
on_path[x][y] = 1;
extended_path.emplace_back(n, m);
return 1;
}
if(!vis[x][y+1]) {
int ret = dfs(x, y+1);
if(ret) {
on_path[x][y] = 1;
extended_path.emplace_back(x, y);
return 1;
}
}
if(!vis[x+1][y]) {
int ret = dfs(x+1, y);
if(ret) {
on_path[x][y] = 1;
extended_path.emplace_back(x, y);
return 1;
}
}
vis[x][y] = 1;
return 0;
}
void update(int x, int y) {
vis[x][y] = 1;
bool flag = 0;
int p, q;
tie(p, q) = prv(x, y);
do {
place : ;
// cerr << '\t' << "pq = " << p << ' ' << q << endl;
if(nxt(p, q) == 2) {
if(p == 1 and q == 1){
break;
}
tie(p, q) = prv(p, q);
goto place;
}
int pp = p+1, qq = q;
if(!vis[pp][qq] and dfs(pp, qq)) {
// cerr << "\tgot it!" << endl;
while(path.back() != ii(p, q)) {
ii pa = path.back();
on_path[pa.fi][pa.se] = 0;
path.pop_back();
}
while(extended_path.size()) {
ii pa = extended_path.back();
path.push_back(pa);
on_path[pa.fi][pa.se] = 1;
extended_path.pop_back();
}
flag = true;
break;
}
} while(p != 1 or q != 1);
if(!flag) vis[x][y] = 0;
// cerr << "flag = " << flag << endl;
// if(x == 2 and y == 2) vis[2][1] = 0;
return flag;
}*/
inline void print(bool wot) {
out[ptr++] = wot ? '1' : '0';
out[ptr++] = '\n';
}
int main(int argc, char const *argv[])
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
scanf("%d %d", &UR::n, &UR::m);
LL::set_nm(UR::n, UR::m);
n = UR::n, m = UR::m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
int x; scanf("%d", &x);
UR::set_cell(i, j, x);
LL::set_cell(i, j, x);
}
}
for(int i = 0; i <= n+1; ++i) {
// vis[i][0] = vis[i][m+1] = 1;
UR::set_cell(i, 0, 1);
UR::set_cell(i, m+1, 1);
LL::set_cell(i, 0, 1);
LL::set_cell(i, m+1, 1);
}
for(int i = 0; i <= n+1; ++i) {
// vis[0][i] = vis[n+1][i] = 1;
UR::set_cell(0, i, 1);
UR::set_cell(n+1, i, 1);
LL::set_cell(0, i, 1);
LL::set_cell(n+1, i, 1);
}
int q; scanf("%d", &q);
/*dfs(1, 1);
path = extended_path;
reverse(all(path));
extended_path.clear();*/
UR::init();
LL::init();
/*cerr << "UR vis:\n";
print_arr(UR::vis);
cerr << "UR on_path:\n";
print_arr(UR::on_path);*/
/*cerr << "LL vis:\n";
print_arr(LL::vis);
cerr << "LL on_path:\n";
print_arr(LL::on_path);*/
// print_arr(on_path);
while(q--) {
int x, y;
scanf("%d %d", &x, &y);
if(UR::get_on_path(x, y) and LL::get_on_path(x, y)) {
print(false);
} else {
UR::destroy(x, y);
LL::destroy(x, y);
print(true);
}
// cerr << "Another query completed:" << endl;
/*cerr << "UR vis:\n";
print_arr(UR::vis);
cerr << "UR on_path:\n";
print_arr(UR::on_path);*/
/*cerr << "LL vis:\n";
print_arr(LL::vis);
cerr << "LL on_path:\n";
print_arr(LL::on_path);*/
/*if(!on_path[x][y]) {
print(true);
// cerr << "true" << endl;
vis[x][y] = 1;
} else {
// cerr << "on path!" << endl;
print(update(x, y));
// cerr << "false" << endl;
}
// cerr << "path ----> " << endl;
// print_arr(on_path);
// cerr << "vis ----> " << endl;
// print_arr(vis);*/
}
out[ptr++] = '\0';
printf("%s", out);
return 0;
}
Compilation message
furniture.cpp: In function 'void UR::update(int, int)':
furniture.cpp:76:9: warning: unused variable 'cnt' [-Wunused-variable]
76 | int cnt = 10;
| ^~~
furniture.cpp: In function 'void LL::update(int, int)':
furniture.cpp:176:9: warning: unused variable 'cnt' [-Wunused-variable]
176 | int cnt = 10;
| ^~~
furniture.cpp: In function 'int main(int, const char**)':
furniture.cpp:328:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
328 | scanf("%d %d", &UR::n, &UR::m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:335:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
335 | int x; scanf("%d", &x);
| ~~~~~^~~~~~~~~~
furniture.cpp:354:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
354 | int q; scanf("%d", &q);
| ~~~~~^~~~~~~~~~
furniture.cpp:378:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
378 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
640 KB |
Output is correct |
| 3 |
Correct |
3 ms |
768 KB |
Output is correct |
| 4 |
Correct |
5 ms |
896 KB |
Output is correct |
| 5 |
Correct |
4 ms |
768 KB |
Output is correct |
| 6 |
Correct |
4 ms |
824 KB |
Output is correct |
| 7 |
Correct |
4 ms |
768 KB |
Output is correct |
| 8 |
Correct |
4 ms |
768 KB |
Output is correct |
| 9 |
Correct |
4 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
640 KB |
Output is correct |
| 3 |
Correct |
3 ms |
768 KB |
Output is correct |
| 4 |
Correct |
5 ms |
896 KB |
Output is correct |
| 5 |
Correct |
4 ms |
768 KB |
Output is correct |
| 6 |
Correct |
4 ms |
824 KB |
Output is correct |
| 7 |
Correct |
4 ms |
768 KB |
Output is correct |
| 8 |
Correct |
4 ms |
768 KB |
Output is correct |
| 9 |
Correct |
4 ms |
768 KB |
Output is correct |
| 10 |
Correct |
14 ms |
2432 KB |
Output is correct |
| 11 |
Correct |
4 ms |
896 KB |
Output is correct |
| 12 |
Correct |
217 ms |
5448 KB |
Output is correct |
| 13 |
Correct |
89 ms |
4216 KB |
Output is correct |
| 14 |
Correct |
391 ms |
7288 KB |
Output is correct |
| 15 |
Correct |
382 ms |
7416 KB |
Output is correct |
| 16 |
Correct |
388 ms |
7800 KB |
Output is correct |
| 17 |
Correct |
509 ms |
8224 KB |
Output is correct |
| 18 |
Correct |
416 ms |
8056 KB |
Output is correct |
| 19 |
Correct |
417 ms |
8316 KB |
Output is correct |
| 20 |
Correct |
338 ms |
8440 KB |
Output is correct |
| 21 |
Correct |
330 ms |
8312 KB |
Output is correct |
