Submission #303385

#	Time	Username	Problem	Language	Result	Execution time	Memory
303385		polipolinom	Furniture (JOI20_furniture)	C++14	100 / 100	3423 ms	20404 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1042;
int c[MAX_N][MAX_N];
int ans[MAX_N][MAX_N];
int sum[MAX_N * 2];

void add (queue < pair < int, int > >& q, int x, int y) {
    if (ans[x][y] == 1) {
        //cout << x << " " << y << endl;
        ans[x][y] = 0;
        sum[x + y]--;
        q.push({x, y});
    }
}

int change(int x, int y) {
    if (ans[x][y] == 0) {
        return 1;
    }
    if (sum[x + y] == 1) {
        return 0;
    }
    queue < pair < int, int > > q;
    add(q, x, y);
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        if (ans[x - 1][y + 1] == 0) {
            add(q, x - 1, y);
            add(q, x, y + 1);
        }
        if (ans[x + 1][y - 1] == 0) {
            add(q, x + 1, y);
            add(q, x, y - 1);
        }
    }
    return 1;
}

int main() {
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sum[i + j]++;
            ans[i][j] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
            if (c[i][j]) {
                change(i, j);
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        cout << change(i, j) << "\n";
    }
    return 0;
}

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