Submission #1207905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207905		jasonic	The Collection Game (BOI21_swaps)	C++20	100 / 100	2 ms	428 KiB

swaps

#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
#define cerr if(0) cout

vector<int> a;
vector<pair<int, int>> visits;
vector<int> idx;
vector<int> whereis;
int n;
int calls = 0;

void interact(int i, int j) {
    if(i >= n || j >= n) return;
    schedule(idx[i]+1, idx[j]+1);
    visits.push_back({idx[i], idx[j]});
    calls++;
}

void visitFix() {
    vector<int> a = visit();
    for(int i = 0; i < calls; i++) {
        if(a[i] == 0) {
            swap(idx[whereis[visits[i].first]], idx[whereis[visits[i].second]]);
            swap(whereis[visits[i].first], whereis[visits[i].second]);
        }
    }

    calls = 0;
    visits = vector<pair<int, int>>();

    cerr << "\n\n";
    for(auto &i : idx) cerr << i << ' ';
    cerr << "\n\n";
}

int lg2(int n) {
    int res = 0;
    while(n != 1) {n>>=1; res++;}
    return res;
}

void fix(int sz) {
    for(int i = 1; i < sz; i <<= 1) { // block size
        // across
        for(int j = 0; j*i*2 < n; j += 1) {
            for(int k = 0; k < i && k + j*i*2 < n; k++) {
                interact(j*i*2 + i - k - 1, k + j*i*2 + i);
            }
        }
        visitFix();

        if(i != 1) for(int j = i/2; j > 0; j >>= 1) {
            for(int k = 0; k*j*2 < n; k++) {
                for(int l = 0; l < j && l + k*j*2 < n; l++) {
                    interact(k*j*2 + l, k*j*2 + l + j);
                }
            }
            visitFix();
        }
    }
}

void solve(int N, int v) {
    n = N;
    int betN = 1<<lg2(n);
    if(betN < n) betN *= 2;
    for(int i = 0; i < n; i++) idx.push_back(i);
    for(int i = 0; i < n; i++) whereis.push_back(i);

    a = vector<int>(n);

    fix(betN);

    for(int i = 0; i < n; i++) a[i] = idx[i]+1;

    answer(a);
}

• 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