oj.uz

Submission #416453

# Submission time Handle Problem Language Result Execution time Memory
416453 2021-06-02T12:05:02 Z KoD The Collection Game (BOI21_swaps) C++17
100 / 100
 9 ms 416 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 M = 1 << logn;
    ord.resize(M, 0);
    for (int h = 1; h <= logn; ++h) {
        for (int t = h - 1; t >= 0; --t) {
            for (int i = 0; i < M; ++i) {
                const int j = i ^ (1 << t);
                if (i < j) {
                    if (ord[i] == 0 or ord[j] == 0) {
                        if ((i >> h & 1) ^ (ord[i] == 0)) {
                            std::swap(ord[i], ord[j]);
                        }
                    } else {
                        schedule(ord[i], ord[j]);
                    }
                }
            }
            const auto resp = visit();
            int idx = 0;
            for (int i = 0; i < M; ++i) {
                const int j = i ^ (1 << t);
                if (i < j and ord[i] != 0 and ord[j] != 0) {
                    if (!((i >> h & 1) ^ resp[idx++])) {
                        std::swap(ord[i], ord[j]);
                    }
                }
            }
        }
    }
    ord.resize(N);
    answer(ord);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.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 5 ms 300 KB Correct
5 Correct 5 ms 300 KB Correct
6 Correct 7 ms 300 KB Correct
7 Correct 5 ms 300 KB Correct
8 Correct 5 ms 304 KB Correct
9 Correct 7 ms 300 KB Correct
10 Correct 6 ms 300 KB Correct
11 Correct 6 ms 292 KB Correct
12 Correct 5 ms 296 KB Correct
13 Correct 6 ms 296 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 3 ms 200 KB Correct
3 Correct 4 ms 200 KB Correct
4 Correct 7 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 3 ms 200 KB Correct
3 Correct 4 ms 200 KB Correct
4 Correct 7 ms 300 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 2 ms 200 KB Correct
7 Correct 4 ms 200 KB Correct
8 Correct 7 ms 304 KB Correct
9 Correct 6 ms 292 KB Correct
10 Correct 6 ms 324 KB Correct
11 Correct 6 ms 300 KB Correct
12 Correct 6 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 300 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 8 ms 300 KB Correct
5 Correct 5 ms 288 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 8 ms 300 KB Correct
5 Correct 5 ms 288 KB Correct
6 Correct 1 ms 200 KB Correct
7 Correct 5 ms 200 KB Correct
8 Correct 3 ms 200 KB Correct
9 Correct 5 ms 296 KB Correct
10 Correct 6 ms 312 KB Correct
11 Correct 6 ms 296 KB Correct
12 Correct 5 ms 304 KB Correct
13 Correct 7 ms 300 KB Correct
14 Correct 6 ms 300 KB Correct
15 Correct 5 ms 292 KB Correct
16 Correct 6 ms 304 KB Correct
17 Correct 6 ms 300 KB Correct
18 Correct 5 ms 296 KB Correct
19 Correct 1 ms 200 KB Correct
20 Correct 2 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 0 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 5 ms 300 KB Correct
5 Correct 7 ms 284 KB Correct
6 Correct 7 ms 280 KB Correct

Subtask #10
14.0 / 14.0

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

Subtask #11
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 5 ms 292 KB Correct
5 Correct 6 ms 280 KB Correct
6 Correct 6 ms 280 KB Correct
7 Correct 8 ms 268 KB Correct

Subtask #12
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 5 ms 292 KB Correct
5 Correct 6 ms 280 KB Correct
6 Correct 6 ms 280 KB Correct
7 Correct 8 ms 268 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 6 ms 292 KB Correct
13 Correct 6 ms 296 KB Correct
14 Correct 6 ms 304 KB Correct
15 Correct 5 ms 296 KB Correct
16 Correct 6 ms 324 KB Correct
17 Correct 5 ms 296 KB Correct
18 Correct 6 ms 296 KB Correct
19 Correct 6 ms 416 KB Correct
20 Correct 7 ms 296 KB Correct
21 Correct 6 ms 292 KB Correct
22 Correct 1 ms 200 KB Correct
23 Correct 3 ms 200 KB Correct
24 Correct 4 ms 244 KB Correct
25 Correct 7 ms 412 KB Correct
26 Correct 7 ms 296 KB Correct
27 Correct 6 ms 284 KB Correct
28 Correct 8 ms 276 KB Correct