Submission #1206134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206134		jer033	The Collection Game (BOI21_swaps)	C++20	100 / 100	2 ms	536 KiB

swaps

#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

vector<vector<pii>> comparisons;

void call_in(int i, int j, int round)
{
    //cout << "calling in " << i << ' ' << j << ' ' << round << '\n';
    comparisons[round].push_back({i, j});
}

void group_call_in(int i, int j, int round)
{
    if (i!=j)
    {
        int mid = (i+j)/2;
        int diff = mid-i+1;
        for (int k=i; k<=mid; k++)
            call_in(k, k+diff, round);
        if ((j-i)>1)
        {
            group_call_in(i, mid, round+1);
            group_call_in(mid+1, j, round+1);
        }
    }
}

void sortpow2(int lo, int hi, int major_round)
{
    int mid = (lo+hi)/2;
    if ((hi-lo)>1)
    {
        sortpow2(lo, mid, major_round-1);
        sortpow2(mid+1, hi, major_round-1);
    }
    int first_round_in_major_round = ((major_round-1)*(major_round))/2;
    for (int i=lo; i<=mid; i++)
        call_in(i, lo+hi-i, first_round_in_major_round);
    group_call_in(lo, mid, first_round_in_major_round+1);
    group_call_in(mid+1, hi, first_round_in_major_round+1);
}

void init()
{
    int K = 512;
    comparisons = vector<vector<pii>> (45);
    sortpow2(1, 512, 9);
}

void solve(int N, int V) {
    init();

    vector<int> beauty;
    for (int i=1; i<=N; i++)
        beauty.push_back(i);
    
    for (int i=0; i<45; i++)
    {
        vector<pii> actual_comparisons;
        for (pii x: comparisons[i])
        {
            int x1 = x.first;
            int x2 = x.second;
            if ((x1<=N) and (x2<=N))
            {
                schedule(beauty[x1-1], beauty[x2-1]);
                actual_comparisons.push_back({x1, x2});
            }
        }
        vector<int> responses = visit();
        int k = responses.size();
        for (int j=0; j<k; j++)
        {
            int x1 = actual_comparisons[j].first;
            int x2 = actual_comparisons[j].second;
            if (responses[j]==0)
                swap(beauty[x1-1], beauty[x2-1]);
        }
    }
    answer(beauty);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3-1: 3 / 3
• Subtask 3-2: 2 / 2
• Subtask 4-1: 9 / 9
• Subtask 4-2: 6 / 6
• Subtask 5-1: 9 / 9
• Subtask 5-2: 6 / 6
• Subtask 6-1: 21 / 21
• Subtask 6-2: 14 / 14
• Subtask 7-1: 9 / 9
• Subtask 7-2: 6 / 6