oj.uz

Submission #495303

# Submission time Handle Problem Language Result Execution time Memory
495303 2021-12-18T10:18:56 Z 600Mihnea Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 18444 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 848 KB Output is correct
2 Correct 6 ms 968 KB Output is correct
3 Correct 37 ms 1040 KB Output is correct
4 Correct 53 ms 1112 KB Output is correct
5 Correct 64 ms 1148 KB Output is correct
6 Correct 106 ms 1224 KB Output is correct
7 Correct 13 ms 1104 KB Output is correct
8 Correct 14 ms 1104 KB Output is correct
9 Correct 17 ms 1184 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 848 KB Output is correct
2 Correct 6 ms 968 KB Output is correct
3 Correct 37 ms 1040 KB Output is correct
4 Correct 53 ms 1112 KB Output is correct
5 Correct 64 ms 1148 KB Output is correct
6 Correct 106 ms 1224 KB Output is correct
7 Correct 13 ms 1104 KB Output is correct
8 Correct 14 ms 1104 KB Output is correct
9 Correct 17 ms 1184 KB Output is correct
10 Correct 69 ms 1488 KB Output is correct
11 Correct 31 ms 840 KB Output is correct
12 Execution timed out 5011 ms 18444 KB Time limit exceeded
13 Halted 0 ms 0 KB -