oj.uz

Submission #297476

# Submission time Handle Problem Language Result Execution time Memory
297476 2020-09-11T15:14:43 Z fedoseevtimofey Furniture (JOI20_furniture) C++14
100 / 100
 464 ms 24068 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
 
using namespace std;
 
typedef long long ll;
 
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, m;
  cin >> n >> m;
  vector <vector <int>> c(n, vector <int> (m));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> c[i][j];
      c[i][j] ^= 1;
    }
  }
  vector <vector <int>> from_start(n, vector <int> (m)), from_finish(n, vector <int> (m));
  from_start[0][0] = 1;
  from_finish[n - 1][m - 1] = 1;
  auto is_ok_start = [&] (int i, int j) {
    int ok = 0;
    if (i > 0) ok |= from_start[i - 1][j];
    if (j > 0) ok |= from_start[i][j - 1];
    return ok;
  };
  auto is_ok_finish = [&] (int i, int j) {
    int ok = 0;
    if (i + 1 < n) ok |= from_finish[i + 1][j];
    if (j + 1 < m) ok |= from_finish[i][j + 1];
    return ok;
  };
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (i == 0 && j == 0) continue;
      from_start[i][j] = c[i][j] & is_ok_start(i, j);
    }
  }
  for (int i = n - 1; i >= 0; --i) {
    for (int j = m - 1; j >= 0; --j) {
      if (i == n - 1 && j == m - 1) continue;
      from_finish[i][j] = c[i][j] & is_ok_finish(i, j);
    }
  }
  /*for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cout << from_finish[i][j] << ' ';
    }
    cout << '\n';
  }*/
  auto ok = [&] (int i, int j) {
    return from_start[i][j] & from_finish[i][j];
  };
  vector <int> cnt(n + m - 1);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (ok(i, j)) {
        ++cnt[i + j];
      }
    }
  }
  function <void(int, int)> kill_start = [&] (int i, int j) {
    if (from_start[i][j] == 0) return;
    if (ok(i, j)) --cnt[i + j];
    from_start[i][j] = 0;
    if (i + 1 < n && from_start[i + 1][j] == 1 && !is_ok_start(i + 1, j)) kill_start(i + 1, j);
    if (j + 1 < m && from_start[i][j + 1] == 1 && !is_ok_start(i, j + 1)) kill_start(i, j + 1);
  };
  function <void(int, int)> kill_finish = [&] (int i, int j) {
    if (from_finish[i][j] == 0) return;
    if (ok(i, j)) --cnt[i + j];
    from_finish[i][j] = 0;
    if (i > 0 && from_finish[i - 1][j] == 1 && !is_ok_finish(i - 1, j)) kill_finish(i - 1, j);
    if (j > 0 && from_start[i][j - 1] == 1 && !is_ok_finish(i, j - 1)) kill_finish(i, j - 1);
  };
  int q;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    if (ok(x, y) && cnt[x + y] == 1) {
      cout << "0\n";
      continue;
    }
    cout << "1\n";
    kill_start(x, y);
    kill_finish(x, y);
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 12 ms 1280 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 241 ms 16248 KB Output is correct
13 Correct 80 ms 12536 KB Output is correct
14 Correct 423 ms 20524 KB Output is correct
15 Correct 448 ms 20320 KB Output is correct
16 Correct 464 ms 21976 KB Output is correct
17 Correct 447 ms 23272 KB Output is correct
18 Correct 434 ms 22648 KB Output is correct
19 Correct 458 ms 24068 KB Output is correct
20 Correct 329 ms 23984 KB Output is correct
21 Correct 448 ms 23976 KB Output is correct