Submission #416453

#	Time	Username	Problem	Language	Result	Execution time	Memory
416453		KoD	The Collection Game (BOI21_swaps)	C++17	100 / 100	9 ms	416 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 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 / 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