Submission #310076

#	Time	Username	Problem	Language	Result	Execution time	Memory
310076		adrianbudau	Furniture (JOI20_furniture)	C++17	100 / 100	2704 ms	14612 KiB

furniture

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int N, M; cin >> N >> M;
    vector< vector<int> > blocked(N, vector<int>(M, 0)), out = blocked, in = blocked;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j) {
            if (j + 1 < M) {
                out[i][j]++;
                in[i][j + 1]++;
            }
            if (i + 1 < N) {
                out[i][j]++;
                in[i + 1][j]++;
            }
        }

    vector<int> leftmost(N + M, N), rightmost(N + M, 0);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j) {
            leftmost[i + j] = min(leftmost[i + j], i);
            rightmost[i + j] = max(rightmost[i + j], i);
        }

    queue< pair<int, int> > Q;
    auto block = [&](int x, int y) {
        Q.emplace(x, y);

        while (!Q.empty()) {
            auto [x, y] = Q.front();
            Q.pop();

            if (blocked[x][y])
                continue;
            blocked[x][y] = 1;
            if (x > 0 && --out[x - 1][y] == 0) {
                Q.emplace(x - 1, y);
            }
            if (y > 0 && --out[x][y - 1] == 0) {
                Q.emplace(x, y - 1);
            }

            if (x + 1 < N && --in[x + 1][y] == 0) {
                Q.emplace(x + 1, y);
            }
            if (y + 1 < M && --in[x][y + 1] == 0) {
                Q.emplace(x, y + 1);
            }

            while (leftmost[x + y] == x && blocked[x][y]) {
                ++leftmost[x + y];
                ++x;
                --y;
            }
            while (rightmost[x + y] == x && blocked[x][y]) {
                --rightmost[x + y];
                --x;
                ++y;
            }
        }
    };

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j) {
            int x; cin >> x;
            if (x == 1)
                block(i, j);
        }

    int K; cin >> K;
    while (K--) {
        int x, y; cin >> x >> y;
        --x; --y;
        if (leftmost[x + y] == x && rightmost[x + y] == x) {
            cout << 0 << "\n";
            continue;
        }
        cout << 1 << "\n";
        block(x, y);
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95