제출 #495303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
495303		600Mihnea	Furniture (JOI20_furniture)	C++17	5 / 100	5011 ms	18444 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int M = 1111111121;


int add(int a, int b) {
  a += b;
  if (a >= M) {
    return a - M;
  }
  if (a < 0) {
    return a + M;
  }
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % M;
}

void addup(int &a, int b) {
  a = add(a, b);
}

void mulup(int &a, int b) {
  a = mul(a, b);
}

const int N = 1000 + 7;
vector<pair<int, int>> d[2 * N];
int n, m, a[N][N];
bool ok1[N][N];
bool ok2[N][N];

void compute() {
  ok1[0][1] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      ok1[i][j] = (a[i][j] == 0 && (ok1[i - 1][j] || ok1[i][j - 1]));
    }
  }
  ok2[n][m + 1] = 1;
  for (int i = n; i >= 1; i--) {
    for (int j = m; j >= 1; j--) {
      ok2[i][j] = (a[i][j] == 0 && (ok2[i + 1][j] || ok2[i][j + 1]));
    }
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      d[i + j].push_back({i, j});
    }
  }
  compute();
  int q;
  cin >> q;
  while (q--) {
    int r, c;
    cin >> r >> c;
    if (ok1[r][c] == 0 || ok2[r][c] == 0) {
      a[r][c] = 1;
    } else {
      assert(ok1[r][c] == 1);
      assert(ok2[r][c] == 1);
      int pos = r + c, cnt = 0;
      for (auto &it : d[pos]) {
        int x = it.first, y = it.second;
        if (ok1[x][y] && ok2[x][y]) {
          cnt++;
        }
      }
      assert(cnt >= 1);
      if (cnt >= 2) {
        a[r][c] = 1;
        compute();
      }
    }


    cout << a[r][c] << "\n";
  }
}

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