Submission #552070

#	Time	Username	Problem	Language	Result	Execution time	Memory
552070		RaresFelix	Furniture (JOI20_furniture)	C++17	100 / 100	284 ms	18300 KiB

furniture

#include <bits/stdc++.h>
#define MN 1021
#pragma GCC optimize("O3,avx2")

using namespace std;
int n, m, Val[MN][MN];
bool C[MN][MN], VI[MN][MN], VF[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 || c > 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(!Activ[l][c]) return 0;
    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() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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;
}

Compilation message (stderr)

furniture.cpp:3:31: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("O3,avx2")
      |                               ^
furniture.cpp:10:28: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   10 | void update_VI(int l, int c) {
      |                            ^
furniture.cpp:21:28: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   21 | void update_VF(int l, int c) {
      |                            ^
furniture.cpp:33:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   33 | bool run(int l, int c) {
      |                      ^
furniture.cpp:51:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   51 | int main() {
      |          ^

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