Submission #888580

#	Time	Username	Problem	Language	Result	Execution time	Memory
888580		box	Furniture (JOI20_furniture)	C++17	100 / 100	205 ms	16220 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 1e3;

int n, m, q;
int c[N][N], cnt[N * 2];

bool del(int i, int j) {
    if (!c[i][j] || cnt[i + j] == 1) return false;
    cnt[i + j]--;
    c[i][j] = 0;
    if (i + 1 < n && (j == 0 || c[i + 1][j - 1] == 0)) del(i + 1, j);
    if (i - 1 >= 0 && (j == m - 1 || c[i - 1][j + 1] == 0)) del(i - 1, j);
    if (j + 1 < m && (i == 0 || c[i - 1][j + 1] == 0)) del(i, j + 1);
    if (j - 1 >= 0 && (i == n - 1 || c[i + 1][j - 1] == 0)) del(i, j - 1);
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) c[i][j] = 1, cnt[i + j]++;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        int a; cin >> a;
        if (a) del(i, j);
    }
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y, x--, y--;
        del(x, y);
        cout << 1 - c[x][y] << '\n';
    }
}

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