oj.uz

Submission #899410

# Submission time Handle Problem Language Result Execution time Memory
899410 2024-01-06T05:00:14 Z Keys Furniture (JOI20_furniture) C++14
100 / 100
 255 ms 19856 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define mp make_pair
#define ar array
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n'
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = a; i >= b; i--)
#define trav(i, a) for (auto& i : a)
template <class T> istream &operator>>(istream& in, vector<T> &v) {trav(i, v) in >> i; return in;}

#ifdef LOCAL
#include "../../lib/debug.h"
#else
#define dbg(...)
#endif

const int N = 1000 + 5;
int a[N][N]; // maintain whether we can reach end
int d[2 * N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m;

void upd(int x, int y) {
  d[x + y]--;
  a[x][y] = 1;
  FOR(i, 0, 4) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (!(nx <= 0 or nx > n or ny <= 0 or ny > m) and !a[nx][ny] and
        ((a[nx + 1][ny] and a[nx][ny + 1] and mp(nx, ny) != mp(n, m)) or (a[nx - 1][ny] and a[nx][ny - 1] and mp(nx, ny) != mp(1ll, 1ll)))) {
      upd(nx, ny);
    }
  }
}


signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  FOR(i, 0, n + 2) FOR(j, 0, m + 2) a[i][j] = 1;
  FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
    a[i][j] = 0;
    d[i + j]++;
  }

  FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
    int x; cin >> x;
    if (x and !a[i][j]) upd(i, j);
  }
  // FOR(i, 1, n + 1) {FOR(j, 1, m + 1) cout << a[i][j] << " "; cout << endl;}

  int q; cin >> q; while (q--) {
    int i, j; cin >> i >> j; 
    if (a[i][j] == 1) cout << 1 << endl;
    else if (d[i + j] == 1) cout << 0 << endl;
    else cout << 1 << endl, upd(i, j);
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 3 ms 2904 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 3 ms 2904 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 7 ms 3032 KB Output is correct
11 Correct 2 ms 2904 KB Output is correct
12 Correct 100 ms 12892 KB Output is correct
13 Correct 41 ms 9692 KB Output is correct
14 Correct 191 ms 17480 KB Output is correct
15 Correct 255 ms 17488 KB Output is correct
16 Correct 202 ms 18564 KB Output is correct
17 Correct 219 ms 19540 KB Output is correct
18 Correct 218 ms 19196 KB Output is correct
19 Correct 244 ms 19856 KB Output is correct
20 Correct 231 ms 19840 KB Output is correct
21 Correct 216 ms 19792 KB Output is correct