Submission #303771

#TimeUsernameProblemLanguageResultExecution timeMemory
303771dsabolicFurniture (JOI20_furniture)C++17
5 / 100
260 ms20532 KiB
#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[N]; int dpath[N][N]; bool dcan[N][N]; pii dloc[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"); upd_upper(i, j); 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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...