oj.uz

Submission #552069

# Submission time Handle Problem Language Result Execution time Memory
552069 2022-04-22T11:30:25 Z RaresFelix Furniture (JOI20_furniture) C++17
100 / 100
 694 ms 40940 KB 
#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 || 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() {
    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 3 ms 2388 KB Output is correct
3 Correct 4 ms 2260 KB Output is correct
4 Correct 6 ms 2496 KB Output is correct
5 Correct 7 ms 2644 KB Output is correct
6 Correct 7 ms 2624 KB Output is correct
7 Correct 7 ms 2644 KB Output is correct
8 Correct 7 ms 2644 KB Output is correct
9 Correct 6 ms 2720 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 3 ms 2388 KB Output is correct
3 Correct 4 ms 2260 KB Output is correct
4 Correct 6 ms 2496 KB Output is correct
5 Correct 7 ms 2644 KB Output is correct
6 Correct 7 ms 2624 KB Output is correct
7 Correct 7 ms 2644 KB Output is correct
8 Correct 7 ms 2644 KB Output is correct
9 Correct 6 ms 2720 KB Output is correct
10 Correct 20 ms 2172 KB Output is correct
11 Correct 5 ms 1492 KB Output is correct
12 Correct 333 ms 28576 KB Output is correct
13 Correct 143 ms 23348 KB Output is correct
14 Correct 577 ms 36388 KB Output is correct
15 Correct 598 ms 36392 KB Output is correct
16 Correct 620 ms 38424 KB Output is correct
17 Correct 647 ms 40100 KB Output is correct
18 Correct 622 ms 38928 KB Output is correct
19 Correct 663 ms 40940 KB Output is correct
20 Correct 621 ms 40788 KB Output is correct
21 Correct 694 ms 40824 KB Output is correct