oj.uz

Submission #624635

# Submission time Handle Problem Language Result Execution time Memory
624635 2022-08-08T14:52:35 Z MilosMilutinovic Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 17456 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) {
    for (int i = x; i >= 0; i--) {
      for (int j = y; j >= 0; j--) {
        Update(i, j);
      }
    }
  };
  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 10 ms 468 KB Output is correct
2 Correct 52 ms 444 KB Output is correct
3 Correct 107 ms 488 KB Output is correct
4 Correct 228 ms 544 KB Output is correct
5 Correct 256 ms 548 KB Output is correct
6 Correct 323 ms 560 KB Output is correct
7 Correct 297 ms 568 KB Output is correct
8 Correct 269 ms 560 KB Output is correct
9 Correct 296 ms 568 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 468 KB Output is correct
2 Correct 52 ms 444 KB Output is correct
3 Correct 107 ms 488 KB Output is correct
4 Correct 228 ms 544 KB Output is correct
5 Correct 256 ms 548 KB Output is correct
6 Correct 323 ms 560 KB Output is correct
7 Correct 297 ms 568 KB Output is correct
8 Correct 269 ms 560 KB Output is correct
9 Correct 296 ms 568 KB Output is correct
10 Correct 4267 ms 1452 KB Output is correct
11 Correct 190 ms 540 KB Output is correct
12 Execution timed out 5078 ms 17456 KB Time limit exceeded
13 Halted 0 ms 0 KB -