oj.uz

답안 #495308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
495308 2021-12-18T10:28:57 Z 600Mihnea Furniture (JOI20_furniture) C++17
100 / 100
 351 ms 8752 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1000 + 7;
int cnt[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]));
      cnt[i + j] += (ok1[i][j] & ok2[i][j]);
    }
  }
}

void reconst1(int i, int j) {
  if ((!(1 <= i && 1 <= j && i <= n && j <= m))) {
    return;
  }
  if (!ok1[i][j]) {
    return;
  }
  bool was = (ok1[i][j] && ok2[i][j]);
  ok1[i][j] = (a[i][j] == 0 && (ok1[i - 1][j] || ok1[i][j - 1]));
  if (!ok1[i][j]) {
    if (was) {
      cnt[i + j]--;
    }
    reconst1(i + 1, j);
    reconst1(i, j + 1);
  }
}

void reconst2(int i, int j) {
  if ((!(1 <= i && 1 <= j && i <= n && j <= m))) {
    return;
  }
  if (!ok2[i][j]) {
    return;
  }
  bool was = (ok1[i][j] && ok2[i][j]);
  ok2[i][j] = (a[i][j] == 0 && (ok2[i + 1][j] || ok2[i][j + 1]));
  if (!ok2[i][j]) {
    if (was) {
      cnt[i + j]--;
    }
    reconst2(i - 1, j);
    reconst2(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];
    }
  }
  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 {
      if (cnt[r + c] >= 2) {
        a[r][c] = 1;
        reconst1(r, c);
        reconst2(r, c);
      }
    }


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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 984 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 4 ms 972 KB Output is correct
7 Correct 5 ms 976 KB Output is correct
8 Correct 4 ms 972 KB Output is correct
9 Correct 3 ms 972 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 984 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 4 ms 972 KB Output is correct
7 Correct 5 ms 976 KB Output is correct
8 Correct 4 ms 972 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 11 ms 844 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 145 ms 7524 KB Output is correct
13 Correct 50 ms 6396 KB Output is correct
14 Correct 306 ms 7968 KB Output is correct
15 Correct 250 ms 7876 KB Output is correct
16 Correct 270 ms 8228 KB Output is correct
17 Correct 327 ms 8576 KB Output is correct
18 Correct 276 ms 8404 KB Output is correct
19 Correct 329 ms 8596 KB Output is correct
20 Correct 263 ms 8612 KB Output is correct
21 Correct 351 ms 8752 KB Output is correct