Submission #722800

#	Time	Username	Problem	Language	Result	Execution time	Memory
722800		Johann	The Collection Game (BOI21_swaps)	C++14	100 / 100	7 ms	440 KiB

swaps

//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvb vector<vb>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvpii vector<vpii>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, V;
int nextN;

void genMerge(int level, vvpii &res)
{
    // 2 times initial length = 1 << level ⇒ 1 << (level + 1)
    int len = 1 << level;
    int tot = 1 << (level + 1);
    res.clear();
    while (len >= 1)
    {
        res.push_back(vpii());
        for (int i = len; i < tot; i += 2 * len)
            for (int j = 0; j < len; ++j)
            {
                int a = (i + j) % tot, b = (i + j + len) % tot;
                res.back().push_back({min(a, b), max(a, b)});
            }
        len >>= 1;
    }
}

void solve(int _N, int _V)
{
    N = _N, V = _V;
    nextN = 1;
    while (nextN < N)
        nextN *= 2;
    if (N == 1)
    {
        answer({1});
        return;
    }

    vi A(nextN);
    iota(all(A), 1);
    vvpii pattern;
    for (int pot = 0; (1 << pot) < nextN; ++pot)
    {
        genMerge(pot, pattern);

        for (int j = 0; j < sz(pattern); ++j)
        {
            for (int i = 0; i < N; i += 1 << (pot + 1))
                for (pii tmp : pattern[j])
                    if (A[i + tmp.first] <= N && A[i + tmp.second] <= N)
                        schedule(A[i + tmp.first], A[i + tmp.second]);

            vi ans = visit();
            int idx = 0;

            for (int i = 0; i < N; i += 1 << (pot + 1))
                for (pii tmp : pattern[j])
                    if (A[i + tmp.first] <= N && A[i + tmp.second] <= N)
                        if (!ans[idx++])
                            swap(A[i + tmp.first], A[i + tmp.second]);
        }
    }

    while (sz(A) > N)
        A.pop_back();
    answer(A);
}

• 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