Submission #715655

#	Time	Username	Problem	Language	Result	Execution time	Memory
715655		Farbod	Furniture (JOI20_furniture)	C++17	100 / 100	264 ms	11304 KiB

furniture

/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Mon, 27 Mar 2023 (15:40:12)
*
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, m, par[N][N], c[N][N], cnt[N << 1];
bool vis[N][N];

void del(int i, int j)
{
    if (vis[i][j])
        return;
    vis[i][j] = 1;

    cnt[i + j]--;
    if (i < n - 1) {
        par[i + 1][j]--;
        if (par[i + 1][j] == 0)
            del(i + 1, j);
    }
    if (j < m - 1) {
        par[i][j + 1]--;
        if (par[i][j + 1] == 0)
            del(i, j + 1);
    }
    if (i > 0) {
        c[i - 1][j]--;
        if (c[i - 1][j] == 0)
            del(i - 1, j);
    }
    if (j > 0) {
        c[i][j - 1]--;
        if (c[i][j - 1] == 0)
            del(i, j - 1);
    }

    return;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            par[i][j] = c[i][j] = 2;
            if (i == 0)
                par[i][j]--;
            if (j == 0)
                par[i][j]--;
            if (i == n - 1)
                c[i][j]--;
            if (j == m - 1)
                c[i][j]--;

            cnt[i + j]++;
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            bool x;
            cin >> x;

            if (x)
                del(i, j);
        }

    int q;
    cin >> q;

    while (q--) {
        int i, j;
        cin >> i >> j, i--, j--;

        if (!vis[i][j] && cnt[i + j] == 1)
            cout << "0\n";
        else
            del(i, j), cout << "1\n";
    }

    return 0;
}

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