Submission #1148909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148909		cot7302	Furniture (JOI20_furniture)	C++20	0 / 100	1 ms	324 KiB

furniture

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using i64 = long long;
using namespace std;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& X) {
  for (auto& x : X) {
    is >> x;
  }
  return is;
}

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M; cin >> N >> M;
  const int NM = N * M;
  vec<int> pus(NM), placed(NM);
  auto ii = [&](int i, int j) {
    return (i != 0 && !placed[(i - 1) * M + j]) + (j != 0 && !placed[i * M + j - 1]);
  };
  auto oo = [&](int i, int j) {
    return (i != N - 1 && !placed[(i + 1) * M + j]) + (j != M - 1 && !placed[i * M + j + 1]);
  };
  auto add = [&](int __i, int __j) -> bool {
    auto dfs = [&](auto&& dfs, int x) -> bool {
      if (placed[x]) {
        return false;
      }
      if (pus[x]) {
        return true;
      }
      if (x == NM - 1) {
        return true;
      }
      placed[x] = 1;
      int i = x / M, j = x % M;
      bool fl = false;
      if (i != N - 1) {
        if (ii(i + 1, j) == 0 || oo(i + 1, j) == 0) {
          fl |= dfs(dfs, x + M);
        }
      }
      if (j != M - 1) {
        if (ii(i, j + 1) == 0 || oo(i, j + 1) == 0) {
          fl |= dfs(dfs, x + 1);
        }
      }
      if (fl) {
        placed[x] = 0;
      }
      return fl;
    };
    pus[__i * M + __j] = dfs(dfs, __i * M + __j);
    return !pus[__i * M + __j];
  };
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      int x; cin >> x;
      if (x == 1) {
        add(i, j);
      }
    }
  }
  int q; cin >> q;
  while (q--) {
    int i, j; cin >> i >> j;
    i -= 1, j -= 1;
    cout << add(i, j) << '\n';
  }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95