Submission #416426

#	Time	Username	Problem	Language	Result	Execution time	Memory
416426		KoD	The Collection Game (BOI21_swaps)	C++17	100 / 100	8 ms	396 KiB

swaps

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 9 / 9
• Subtask 6: 6 / 6
• Subtask 7: 9 / 9
• Subtask 8: 6 / 6
• Subtask 9: 21 / 21
• Subtask 10: 14 / 14
• Subtask 11: 9 / 9
• Subtask 12: 6 / 6