Submission #872998

#	Time	Username	Problem	Language	Result	Execution time	Memory
872998		tvladm2009	Furniture (JOI20_furniture)	C++17	100 / 100	292 ms	31828 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e3 + 7;

int a[N][N];
int up[N][N], down[N][N];
int l[N][N], r[N][N];
int n, m;

void update(int x, int y) {
    up[x][y] = 0;
    down[x][y] = 0;
    l[x][y] = 0;
    r[x][y] = 0;
    if (r[x][y - 1]) {
        r[x][y - 1] = 0;
        if (!down[x][y - 1]) {
            update(x, y - 1);
        }
    }
    if (l[x][y + 1]) {
        l[x][y + 1] = 0;
        if (!up[x][y + 1]) {
            update(x, y + 1);
        }
    }
    if (down[x - 1][y]) {
        down[x - 1][y] = 0;
        if (!r[x - 1][y]) {
            update(x - 1, y);
        }
    }
    if (up[x + 1][y]) {
        up[x + 1][y] = 0;
        if (!l[x + 1][y]) {
            update(x + 1, y);
        }
    }
}

int query(int x, int y) {
    if (up[x][y] == 0 && down[x][y] == 0 && l[x][y] == 0 && r[x][y] == 0) {
        return 1;
    }
    bool ok0 = 1, ok1 = 1;
    for (int i = x + 1; i <= n; ++i) {
        if (l[i][y]) {
            ok0 = 0;
            break;
        }
    }
    if (ok0) {
        for (int j = y + 1; j <= m; ++j) {
            if (up[x][j]) {
                ok0 = 0;
                break;
            }
        }
    }
    for (int i = 1; i <= x; ++i) {
        if (r[i][y]) {
            ok1 = 0;
            break;
        }
    }
    if (ok1) {
        for (int j = 1; j <= y; ++j) {
            if (down[x][j]) {
                ok1 = 0;
                break;
            }
        }
    }
    if (ok0 || ok1) {
        return 0;
    }
    update(x, y);
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i == 1 && j == 1) {
                up[i][j] = 1;
                down[i][j] = 1;
                l[i][j] = 1;
                r[i][j] = 1;
                continue;
            }
            up[i][j] = (i > 1);
            down[i][j] = (i < n);
            l[i][j] = (j > 1);
            r[i][j] = (j < m);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j]) {
                update(i, j);
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << query(x, y) << "\n";
    }
    return 0;
}

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