oj.uz

Submission #886345

# Submission time Handle Problem Language Result Execution time Memory
886345 2023-12-11T22:34:22 Z stefanneagu Furniture (JOI20_furniture) C++17
100 / 100
 226 ms 23848 KB 
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e3 + 5;
int jd[nmax][nmax], ss[nmax][nmax], diag[2 * nmax], n, m;
int f[nmax][nmax];
void remo(int i, int j) {
  if (f[i][j]) return;
  f[i][j] = 1, diag[i + j]--;
  if (--jd[i+1][j] == 0) remo(i+1, j);
  if (--jd[i][j+1] == 0) remo(i, j+1);
  if (--ss[i-1][j] == 0) remo(i-1, j);
  if (--ss[i][j-1] == 0) remo(i, j-1);
}
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; f[i][0] = f[i][m+1] = 1, i++) {
    for (int j = 1; j <= m; f[0][j] = f[n+1][j] = 1, j++) {
      diag[i+j]++;
      jd[i+1][j]++, jd[i][j+1]++;
      ss[i-1][j]++, ss[i][j-1]++;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      int x; cin >> x;
      if (x) remo(i, j);
    }
  }
  int q; cin >> q;
  while (q--) {
    int i, j, ans = 0; cin >> i >> j;
    if (diag[i + j] != 1 || f[i][j] == 1)
      remo(i, j), ans = 1;
    cout << ans << "\n";
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 4 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 4 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 7 ms 6744 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 99 ms 12800 KB Output is correct
13 Correct 41 ms 12208 KB Output is correct
14 Correct 218 ms 13728 KB Output is correct
15 Correct 175 ms 21712 KB Output is correct
16 Correct 185 ms 22576 KB Output is correct
17 Correct 188 ms 23376 KB Output is correct
18 Correct 189 ms 22880 KB Output is correct
19 Correct 203 ms 23808 KB Output is correct
20 Correct 203 ms 23792 KB Output is correct
21 Correct 226 ms 23848 KB Output is correct