oj.uz

Submission #624639

# Submission time Handle Problem Language Result Execution time Memory
624639 2022-08-08T14:55:17 Z MilosMilutinovic Furniture (JOI20_furniture) C++14
100 / 100
 565 ms 28040 KB 
/**
 *    author:  wxhtzdy
 *    created: 03.08.2022 13:12:41
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }                
  vector<vector<bool>> dp(n, vector<bool>(m));
  dp[n - 1][m - 1] = true;  
  auto Update = [&](int i, int j) {
    if (a[i][j] == 1) {
      dp[i][j] = false;
      return;
    }
    dp[i][j] = false;
    if (i == n - 1 && j == m - 1) {
      dp[i][j] = true;
    }
    if (i + 1 < n) {
      dp[i][j] = dp[i][j] | dp[i + 1][j];
    }
    if (j + 1 < m) {
      dp[i][j] = dp[i][j] | dp[i][j + 1];
    }
  };
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      Update(i, j);
    }
  }
  vector<vector<vector<int>>> id(2, vector<vector<int>>(n, vector<int>(m, -1)));
  vector<vector<int>> path(2);
  { // right
    int T = 0;
    vector<int> que(1, 0);
    for (int b = 0; b < (int) que.size(); b++) {
      int x = que[b] / m;
      int y = que[b] % m;
      id[0][x][y] = T++;
      if (y < m - 1 && dp[x][y + 1]) {
        que.push_back(x * m + y + 1);
      } else if (x < n - 1) {
        que.push_back((x + 1) * m + y);
      }
    }
    path[0] = que;    
  }
  { // down
    int T = 0;
    vector<int> que(1, 0);
    for (int b = 0; b < (int) que.size(); b++) {
      int x = que[b] / m;
      int y = que[b] % m;
      id[1][x][y] = T++;
      if (x < n - 1 && dp[x + 1][y]) {
        que.push_back((x + 1) * m + y);
      } else if (y < m - 1) {
        que.push_back(x * m + y + 1);
      }
    }
    path[1] = que;    
  }
  auto Go0 = [&](int sx, int sy) {
    int T = id[0][sx][sy];
    for (int b = T; b < (int) path[0].size(); b++) {
      int x = path[0][b] / m;
      int y = path[0][b] % m;
      id[0][x][y] = b;
      if (y + 1 < m && dp[x][y + 1]) {
        path[0].push_back(x * m + y + 1);
      } else if (x + 1 < n) {
        path[0].push_back((x + 1) * m + y);
      }
    }
  };
  auto Go1 = [&](int sx, int sy) {
    int T = id[1][sx][sy];
    for (int b = T; b < (int) path[1].size(); b++) {
      int x = path[1][b] / m;
      int y = path[1][b] % m;
      id[1][x][y] = b;
      if (x + 1 < n && dp[x + 1][y]) {
        path[1].push_back((x + 1) * m + y);
      } else if (y + 1 < m) {
        path[1].push_back(x * m + y + 1);
      }
    }
  };
  function<void(int, int, bool)> Go = [&](int x, int y, bool fir) {
    if (x < 0 || y < 0) {
      return;
    }
    bool f0 = dp[x][y];
    Update(x, y);
    bool f1 = dp[x][y];
    if (!fir && f0 == f1) {
      return;
    }
    Go(x - 1, y, false);
    Go(x, y - 1, false);
  };
  int q;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    bool f0 = (id[0][x][y] == -1);
    bool f1 = (id[1][x][y] == -1);
    if (f0 && f1) {
      cout << 1 << '\n';
      a[x][y] = 1;
      Go(x, y, true);
      continue;
    }
    if (!f0 & !f1) {
      cout << 0 << '\n';
      continue;
    }
    cout << 1 << '\n';
    a[x][y] = 1;
    Go(x, y, true);
    if (!f0) {
      int nx = path[0][id[0][x][y] - 1] / m;              
      int ny = path[0][id[0][x][y] - 1] % m;              
      while (path[0].back() != nx * m + ny) {
        id[0][path[0].back() / m][path[0].back() % m] = -1;
        path[0].pop_back();        
      }
      while (!dp[path[0].back() / m][path[0].back() % m]) {
        id[0][path[0].back() / m][path[0].back() % m] = -1;
        path[0].pop_back();
      }
      nx = path[0].back() / m;
      ny = path[0].back() % m;
      Go0(nx, ny);
    }
    if (!f1) {
      int nx = path[1][id[1][x][y] - 1] / m;              
      int ny = path[1][id[1][x][y] - 1] % m;              
      while (path[1].back() != nx * m + ny) {
        id[1][path[1].back() / m][path[1].back() % m] = -1;
        path[1].pop_back();        
      }
      while (!dp[path[1].back() / m][path[1].back() % m]) {
        id[1][path[1].back() / m][path[1].back() % m] = -1;
        path[1].pop_back();
      }
      nx = path[1].back() / m;
      ny = path[1].back() % m;
      Go1(nx, ny);
    }
  }                                                
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 4 ms 516 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 4 ms 516 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 14 ms 1236 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 239 ms 18004 KB Output is correct
13 Correct 60 ms 16048 KB Output is correct
14 Correct 451 ms 24188 KB Output is correct
15 Correct 508 ms 23672 KB Output is correct
16 Correct 494 ms 25796 KB Output is correct
17 Correct 565 ms 27072 KB Output is correct
18 Correct 496 ms 26256 KB Output is correct
19 Correct 493 ms 27852 KB Output is correct
20 Correct 367 ms 28040 KB Output is correct
21 Correct 468 ms 27896 KB Output is correct