oj.uz

Submission #552070

# Submission time Handle Problem Language Result Execution time Memory
552070 2022-04-22T11:32:27 Z RaresFelix Furniture (JOI20_furniture) C++17
100 / 100
 284 ms 18300 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 3 ms 1148 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 6 ms 1364 KB Output is correct
8 Correct 3 ms 1364 KB Output is correct
9 Correct 3 ms 1364 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 3 ms 1148 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 6 ms 1364 KB Output is correct
8 Correct 3 ms 1364 KB Output is correct
9 Correct 3 ms 1364 KB Output is correct
10 Correct 7 ms 1236 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 142 ms 11884 KB Output is correct
13 Correct 59 ms 9080 KB Output is correct
14 Correct 261 ms 16284 KB Output is correct
15 Correct 245 ms 16348 KB Output is correct
16 Correct 284 ms 17096 KB Output is correct
17 Correct 248 ms 18044 KB Output is correct
18 Correct 281 ms 17500 KB Output is correct
19 Correct 245 ms 18300 KB Output is correct
20 Correct 275 ms 18268 KB Output is correct
21 Correct 245 ms 18220 KB Output is correct