#include <bits/stdc++.h>
#define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
#define X first
#define Y second
using namespace std;
using pii = pair<int, int>;
const int N = 1e3 + 500;
const int dy[2] = {1, 0};
const int dx[2] = {0, 1};
int n, m;
int mat[N][N];
int upath[N][N];
bool ucan[N][N];
pii uloc[2 * N];
int dpath[N][N];
bool dcan[N][N];
pii dloc[2 * N];
bool find_upper(int x, int y, int t) {
if(!ucan[x][y]) return 0;
assert(!upath[x][y] || upath[x][y] == t);
if(upath[x][y]) {
//printf("doso kraj (%d,%d)\n", x, y);
return 1;
}
if(mat[x][y]) {
//if(x == 1 && y == 1) printf("proso kurcinu\n");
return 0;
}
for(int i = 0; i < 2; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if(nx >= n || ny >= m || mat[nx][ny]) continue;
if(find_upper(nx, ny, t + 1)) {
ucan[x][y] = 1;
upath[uloc[t].X][uloc[t].Y] = 0;
upath[x][y] = t;
uloc[t] = {x, y};
return 1;
//return ucan[x][y] = upath[x][y] = 1;
}
}
//if(x == 0 && y == 0) printf("doso u kurac, %d\n", find_upper(1, 1));
return ucan[x][y] = upath[x][y] = 0;
}
bool find_lower(int x, int y, int t) {
if(!dcan[x][y]) return 0;
assert(!dpath[x][y] || dpath[x][y] == t);
if(dpath[x][y]) {
//printf("doso kraj (%d,%d)\n", x, y);
return 1;
}
if(mat[x][y]) {
//if(x == 1 && y == 1) printf("proso kurcinu\n");
return 0;
}
for(int i = 0; i < 2; ++i) {
int nx = x + dx[1 - i], ny = y + dy[1 - i];
if(nx >= n || ny >= m || mat[nx][ny]) continue;
if(find_lower(nx, ny, t + 1)) {
dcan[x][y] = 1;
dpath[dloc[t].X][dloc[t].Y] = 0;
dpath[x][y] = t;
dloc[t] = {x, y};
return 1;
//return ucan[x][y] = upath[x][y] = 1;
}
}
//if(x == 0 && y == 0) printf("doso u kurac, %d\n", find_upper(1, 1));
return dcan[x][y] = dpath[x][y] = 0;
}
int dbacktrack(int x, int y) {
if(x == 0 && y == 0) return -1;
if(y > 0 && dpath[x][y - 1]) return 0;
if(x > 0 && dpath[x - 1][y]) return 1;
return -1;
}
int backtrack(int x, int y) {
if(x == 0 && y == 0) return -1;
if(x > 0 && upath[x - 1][y]) return 1;
if(y > 0 && upath[x][y - 1]) return 0;
return -1;
}
bool upd_upper(int x, int y) {
mat[x][y] = 1;
if(!upath[x][y]) return 1;
while(1) {
int idx = backtrack(x, y);
if(idx == -1) return 0;
x -= dx[idx], y -= dy[idx];
//printf("trenutno pokusavama (%d,%d)\n", x, y);
//printf("x -> %d, y-> %d\n", x, y);
int tim = upath[x][y];
upath[x][y] = 0;
if(find_upper(x, y, tim)) {
//printf("naso put krecuci od (%d,%d)\n", x, y);
return 1;
}
}
return 1;
}
bool upd_lower(int x, int y) {
mat[x][y] = 1;
if(!dpath[x][y]) return 1;
while(1) {
int idx = dbacktrack(x, y);
if(idx == -1) return 0;
x -= dx[idx], y -= dy[idx];
//printf("trenutno pokusavama (%d,%d)\n", x, y);
//printf("x -> %d, y-> %d, idx %d\n", x, y, idx);
int tim = dpath[x][y];
dpath[x][y] = 0;
if(find_lower(x, y, tim)) {
//printf("naso put krecuci od (%d,%d)\n", x, y);
return 1;
}
}
return 1;
}
void ppath() {
rep(i, 0, n) {
rep(j, 0, m)
printf("%d ", upath[i][j]);
printf("\n");
}
}
int main() {
scanf("%d%d", &n, &m);
int cnt = 1;
rep(i, 0, n) rep(j, 0, m) ucan[i][j] = 1, dcan[i][j] = 1;
rep(i, 0, m) upath[0][i] = cnt, uloc[cnt++] = {0, i};
rep(i, 1, n) upath[i][m - 1] = cnt, uloc[cnt++] = {i, m - 1};
cnt = 1;
rep(i, 0, n) dpath[i][0] = cnt, dloc[cnt++] = {i, 0};
rep(j, 1, m) dpath[n - 1][j] = cnt, dloc[cnt++] = {n - 1, j};
rep(i, 0, n) {
rep(j, 0, m) {
int x;
scanf("%d", &x);
if(x) {
if(upath[i][j] && dpath[i][j]) {
//printf("0\n");
continue;
}
//if(!upd_upper(i, j)) printf("KURCINA\n");
//if(!upd_lower(i, j)) printf("DONJA_KURCINA\n");
assert(upd_upper(i, j));
assert(upd_lower(i, j));
}
}
}
int q;
scanf("%d", &q);
while(q--) {
int x, y;
scanf("%d%d", &x, &y);
--x, --y;
if(upath[x][y] && dpath[x][y]) {
printf("0\n");
continue;
}
printf("1\n");
upd_upper(x, y);
upd_lower(x, y);
}
return 0;
}
Compilation message
furniture.cpp: In function 'bool find_upper(int, int, int)':
furniture.cpp:54:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
54 | return ucan[x][y] = upath[x][y] = 0;
| ~~~~~~~~~~~~^~~
furniture.cpp: In function 'bool find_lower(int, int, int)':
furniture.cpp:88:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
88 | return dcan[x][y] = dpath[x][y] = 0;
| ~~~~~~~~~~~~^~~
furniture.cpp: In function 'void ppath()':
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:150:9: note: in expansion of macro 'rep'
150 | rep(i, 0, n) {
| ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:151:17: note: in expansion of macro 'rep'
151 | rep(j, 0, m)
| ^~~
furniture.cpp: In function 'int main()':
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:161:9: note: in expansion of macro 'rep'
161 | rep(i, 0, n) rep(j, 0, m) ucan[i][j] = 1, dcan[i][j] = 1;
| ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:161:22: note: in expansion of macro 'rep'
161 | rep(i, 0, n) rep(j, 0, m) ucan[i][j] = 1, dcan[i][j] = 1;
| ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:162:9: note: in expansion of macro 'rep'
162 | rep(i, 0, m) upath[0][i] = cnt, uloc[cnt++] = {0, i};
| ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:163:9: note: in expansion of macro 'rep'
163 | rep(i, 1, n) upath[i][m - 1] = cnt, uloc[cnt++] = {i, m - 1};
| ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:166:17: note: in expansion of macro 'rep'
166 | rep(i, 0, n) dpath[i][0] = cnt, dloc[cnt++] = {i, 0};
| ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:167:17: note: in expansion of macro 'rep'
167 | rep(j, 1, m) dpath[n - 1][j] = cnt, dloc[cnt++] = {n - 1, j};
| ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:169:9: note: in expansion of macro 'rep'
169 | rep(i, 0, n) {
| ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
| ^
furniture.cpp:170:17: note: in expansion of macro 'rep'
170 | rep(j, 0, m) {
| ^~~
furniture.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
158 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:172:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
172 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
furniture.cpp:189:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
189 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
furniture.cpp:192:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
192 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1792 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1792 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1792 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1792 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 10 |
Correct |
15 ms |
1664 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 12 |
Correct |
255 ms |
20600 KB |
Output is correct |
| 13 |
Correct |
111 ms |
17528 KB |
Output is correct |
| 14 |
Correct |
510 ms |
20504 KB |
Output is correct |
| 15 |
Correct |
525 ms |
20472 KB |
Output is correct |
| 16 |
Correct |
556 ms |
21112 KB |
Output is correct |
| 17 |
Correct |
632 ms |
22008 KB |
Output is correct |
| 18 |
Correct |
529 ms |
21240 KB |
Output is correct |
| 19 |
Correct |
614 ms |
21752 KB |
Output is correct |
| 20 |
Correct |
404 ms |
21756 KB |
Output is correct |
| 21 |
Correct |
590 ms |
22008 KB |
Output is correct |
