Submission #297476

#	Time	Username	Problem	Language	Result	Execution time	Memory
297476		fedoseevtimofey	Furniture (JOI20_furniture)	C++14	100 / 100	464 ms	24068 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95