oj.uz

Submission #416426

# Submission time Handle Problem Language Result Execution time Memory
416426 2021-06-02T11:30:00 Z KoD The Collection Game (BOI21_swaps) C++17
100 / 100
 8 ms 396 KB 
#include <bits/stdc++.h>
#include "swaps.h"

template <class T> using Vec = std::vector<T>;

void solve(int N, int V) {
    Vec<int> ord(N);
    std::iota(ord.begin(), ord.end(), 1);
    int logn = 0;
    while ((1 << logn) < N) {
        logn += 1;
    }
    const int N2 = 1 << logn;
    ord.resize(N2, 0);
    for (int h = 1; h <= logn; ++h) {
        for (int t = h - 1; t >= 0; --t) {
            const int bit = (1 << t);
            for (int i = 0; i < N2; ++i) {
                if (!(i >> t & 1) and ord[i] != 0 and ord[i + bit] != 0) {
                    schedule(ord[i], ord[i + bit]);
                }
            }
            int idx = 0;
            const auto resp = visit();
            for (int i = 0; i < N2; ++i) {
                if (!(i >> t & 1)) {
                    const auto x = (ord[i] == 0 ? 0 : (ord[i + bit] == 0 ? 1 : resp[idx++]));
                    if (!((i >> h & 1) ^ x)) {
                        std::swap(ord[i], ord[i + bit]);
                    }
                }
            }
        }
    }
    ord.resize(N);
    answer(ord);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 7 ms 296 KB Correct
5 Correct 7 ms 292 KB Correct
6 Correct 8 ms 300 KB Correct
7 Correct 6 ms 300 KB Correct
8 Correct 6 ms 300 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 284 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 5 ms 308 KB Correct
5 Correct 5 ms 300 KB Correct
6 Correct 6 ms 288 KB Correct
7 Correct 6 ms 396 KB Correct
8 Correct 7 ms 304 KB Correct
9 Correct 5 ms 300 KB Correct
10 Correct 6 ms 300 KB Correct
11 Correct 7 ms 296 KB Correct
12 Correct 6 ms 300 KB Correct
13 Correct 5 ms 300 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 1 ms 200 KB Correct
4 Correct 3 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 6 ms 300 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 6 ms 300 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 2 ms 284 KB Correct
7 Correct 3 ms 200 KB Correct
8 Correct 5 ms 296 KB Correct
9 Correct 6 ms 296 KB Correct
10 Correct 5 ms 300 KB Correct
11 Correct 5 ms 304 KB Correct
12 Correct 7 ms 300 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 1 ms 200 KB Correct
15 Correct 3 ms 200 KB Correct
16 Correct 6 ms 296 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 7 ms 292 KB Correct
5 Correct 5 ms 276 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 7 ms 292 KB Correct
5 Correct 5 ms 276 KB Correct
6 Correct 1 ms 200 KB Correct
7 Correct 1 ms 200 KB Correct
8 Correct 3 ms 200 KB Correct
9 Correct 6 ms 300 KB Correct
10 Correct 7 ms 292 KB Correct
11 Correct 5 ms 296 KB Correct
12 Correct 6 ms 300 KB Correct
13 Correct 6 ms 296 KB Correct
14 Correct 6 ms 292 KB Correct
15 Correct 5 ms 296 KB Correct
16 Correct 7 ms 292 KB Correct
17 Correct 6 ms 296 KB Correct
18 Correct 6 ms 296 KB Correct
19 Correct 1 ms 200 KB Correct
20 Correct 1 ms 200 KB Correct
21 Correct 3 ms 200 KB Correct
22 Correct 5 ms 292 KB Correct
23 Correct 6 ms 280 KB Correct

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 6 ms 300 KB Correct
5 Correct 8 ms 296 KB Correct
6 Correct 7 ms 284 KB Correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 6 ms 300 KB Correct
5 Correct 8 ms 296 KB Correct
6 Correct 7 ms 284 KB Correct
7 Correct 1 ms 200 KB Correct
8 Correct 2 ms 200 KB Correct
9 Correct 3 ms 200 KB Correct
10 Correct 7 ms 292 KB Correct
11 Correct 5 ms 304 KB Correct
12 Correct 7 ms 304 KB Correct
13 Correct 6 ms 296 KB Correct
14 Correct 6 ms 296 KB Correct
15 Correct 6 ms 300 KB Correct
16 Correct 6 ms 300 KB Correct
17 Correct 6 ms 300 KB Correct
18 Correct 6 ms 300 KB Correct
19 Correct 6 ms 296 KB Correct
20 Correct 1 ms 200 KB Correct
21 Correct 3 ms 200 KB Correct
22 Correct 2 ms 328 KB Correct
23 Correct 7 ms 296 KB Correct
24 Correct 6 ms 276 KB Correct
25 Correct 6 ms 276 KB Correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 1 ms 280 KB Correct
3 Correct 4 ms 200 KB Correct
4 Correct 6 ms 296 KB Correct
5 Correct 5 ms 296 KB Correct
6 Correct 6 ms 280 KB Correct
7 Correct 6 ms 276 KB Correct

Subtask #12
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 1 ms 280 KB Correct
3 Correct 4 ms 200 KB Correct
4 Correct 6 ms 296 KB Correct
5 Correct 5 ms 296 KB Correct
6 Correct 6 ms 280 KB Correct
7 Correct 6 ms 276 KB Correct
8 Correct 1 ms 200 KB Correct
9 Correct 1 ms 200 KB Correct
10 Correct 2 ms 200 KB Correct
11 Correct 3 ms 200 KB Correct
12 Correct 5 ms 296 KB Correct
13 Correct 7 ms 292 KB Correct
14 Correct 5 ms 296 KB Correct
15 Correct 7 ms 296 KB Correct
16 Correct 7 ms 296 KB Correct
17 Correct 6 ms 300 KB Correct
18 Correct 7 ms 296 KB Correct
19 Correct 6 ms 296 KB Correct
20 Correct 7 ms 296 KB Correct
21 Correct 6 ms 296 KB Correct
22 Correct 2 ms 200 KB Correct
23 Correct 3 ms 200 KB Correct
24 Correct 4 ms 200 KB Correct
25 Correct 6 ms 300 KB Correct
26 Correct 8 ms 280 KB Correct
27 Correct 7 ms 276 KB Correct
28 Correct 7 ms 280 KB Correct