oj.uz

Submission #387507

# Submission time Handle Problem Language Result Execution time Memory
387507 2021-04-08T15:52:20 Z timmyfeng Furniture (JOI20_furniture) C++17
100 / 100
 363 ms 14060 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1000;

bool blocked_s[N][N], blocked_t[N][N];
int unblocked[2 * N], n, m;

void block_s(int x, int y) {
    unblocked[x + y] -= !blocked_t[x][y];
    blocked_s[x][y] = true;
    if (x < n - 1 && !blocked_s[x + 1][y] && (y == 0 || blocked_s[x + 1][y - 1])) {
        block_s(x + 1, y);
    }
    if (y < m - 1 && !blocked_s[x][y + 1] && (x == 0 || blocked_s[x - 1][y + 1])) {
        block_s(x, y + 1);
    }
}

void block_t(int x, int y) {
    unblocked[x + y] -= !blocked_s[x][y];
    blocked_t[x][y] = true;
    if (x > 0 && !blocked_t[x - 1][y] && (y == m - 1 || blocked_t[x - 1][y + 1])) {
        block_t(x - 1, y);
    }
    if (y > 0 && !blocked_t[x][y - 1] && (x == n - 1 || blocked_t[x + 1][y - 1])) {
        block_t(x, y - 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int c;
            cin >> c;

            if (c == 1) {
                if (!blocked_s[i][j]) {
                    block_s(i, j);
                }
                if (!blocked_t[i][j]) {
                    block_t(i, j);
                }
            }

            ++unblocked[i + j];
        }
    }

    int q;
    cin >> q;

    while (q--) {
        int x, y;
        cin >> x >> y;
        --x, --y;

        if (blocked_s[x][y] || blocked_t[x][y]) {
            cout << 1 << "\n";
        } else if (unblocked[x + y] > 1) {
            cout << 1 << "\n";
            block_s(x, y);
            block_t(x, y);
        } else {
            cout << 0 << "\n";
        }
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 4 ms 620 KB Output is correct
6 Correct 5 ms 620 KB Output is correct
7 Correct 4 ms 620 KB Output is correct
8 Correct 5 ms 620 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 11 ms 748 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 167 ms 7020 KB Output is correct
13 Correct 68 ms 4076 KB Output is correct
14 Correct 307 ms 11884 KB Output is correct
15 Correct 311 ms 12268 KB Output is correct
16 Correct 313 ms 12908 KB Output is correct
17 Correct 363 ms 13804 KB Output is correct
18 Correct 329 ms 13164 KB Output is correct
19 Correct 346 ms 13932 KB Output is correct
20 Correct 324 ms 14060 KB Output is correct
21 Correct 355 ms 14060 KB Output is correct