Submission #552061

#	Time	Username	Problem	Language	Result	Execution time	Memory
552061		RaresFelix	Furniture (JOI20_furniture)	C++17	0 / 100	4 ms	2388 KiB

furniture

#include <bits/stdc++.h>
#define MN 1071

using namespace std;
int n, m, C[MN][MN], VI[MN][MN], VF[MN][MN], Val[MN][MN], Activ[MN][MN];
int Frecv[2 * MN];

void update_VI(int l, int c) {
    if(!VI[l][c] || !l || !c || l > n || c > m) return;
    if(VI[l - 1][c] || VI[l][c - 1]) return;
    VI[l][c] = 0;
    if(Activ[l][c]) {
        Activ[l][c] = 0;
        --Frecv[Val[l][c]];
    }
    update_VI(l + 1, c);
    update_VI(l, c  + 1);
}
void update_VF(int l, int c) {
    if(!VF[l][c] || !l || !c || l > n || l > m) return;
    if(VF[l + 1][c] || VF[l][c + 1]) return;
    VF[l][c] = 0;
    if(Activ[l][c]) {
        Activ[l][c] = 0;
        --Frecv[Val[l][c]];
    }
    update_VF(l - 1, c);
    update_VF(l, c - 1);
}

bool run(int l, int c) {
    if(!C[l][c] && !Activ[l][c]) {
        C[l][c] = 1;
        return 1;
    }
    if(Frecv[Val[l][c]] == 1) return 0;
    Activ[l][c] = 0, --Frecv[Val[l][c]];
    VI[l][c] = 0, VF[l][c] = 0;
    update_VI(l, c + 1);
    update_VI(l + 1, c);

    update_VF(l - 1, c);
    update_VF(l, c - 1);
    C[l][c] = 1;
    return 1;
}

int main() {
    cin >> n >> m;
    vector<pair<int, int> > Fake;
    for(int i = 1; i <= n; ++i)
        for(int j = 1, v; j <= m; ++j) {
            VI[i][j] = VF[i][j] = Activ[i][j] = 1;
            Val[i][j] = i + j - 1;
            ++Frecv[Val[i][j]];
            cin >> v;
            if(v) Fake.push_back({i, j});
        }
    int q;
    cin >> q;
    vector<pair<int, int> > Real;
    for(int i = 1, l, c; i <= q; ++i) {
        cin >> l >> c;
        Real.push_back({l, c});
    }
    for(auto [a, b] : Fake) run(a, b);
    for(auto [a, b] : Real) cout << run(a, b) << "\n";
    return 0;
}

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