Submission #595079

#	Time	Username	Problem	Language	Result	Execution time	Memory
595079		elkernos	Furniture (JOI20_furniture)	C++17	100 / 100	253 ms	12188 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> good(n + 2, vector<bool>(m + 2));
    vector<int> cnt(n + m + 1);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            good[i][j] = 1;
            cnt[i + j]++;
        }
    }
    auto put = [&](int X, int Y) {
        if(!good[X][Y]) {
            return 1;
        }
        if(cnt[X + Y] == 1) {
            return 0;
        }
        function<void(int, int)> dfs = [&](int x, int y) {
            auto maybe = [&](int tx, int ty) {
                if(good[tx][ty]) {
                    good[tx][ty] = 0;
                    cnt[tx + ty]--;
                    dfs(tx, ty);
                }
            };
            if(!good[x - 1][y + 1]) {
                maybe(x - 1, y);
                maybe(x, y + 1);
            }
            if(!good[x + 1][y - 1]) {
                maybe(x, y - 1);
                maybe(x + 1, y);
            }
        };
        good[X][Y] = 0;
        cnt[X + Y]--;
        dfs(X, Y);
        return 1;
    };
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int c;
            cin >> c;
            if(c == 1) {
                put(i, j);
            }
        }
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << put(x, y) << '\n';
    }
}

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