Submission #1215044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215044		ProtonDecay314	The Collection Game (BOI21_swaps)	C++20	20 / 100	5 ms	424 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 <bits/stdc++.h>
#include "swaps.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

void printv(const vi& a) {
    for(int v : a) cerr << v << " ";
    cerr << endl;
}

vi cur_labels;

void schedule_and_visit(const vpi& pairs) {
    if(pairs.size() == 0) return;

    for(auto& [p1, p2] : pairs) {
        schedule(cur_labels[p1] + 1, cur_labels[p2] + 1);
    }

    vi vis_results = visit();

    int ps = pairs.size();

    for(int i = 0; i < ps; i++) {
        if(vis_results[i] == 0) {
            swap(cur_labels[pairs[i].first], cur_labels[pairs[i].second]);
        }
    }
}

void solve(int N, int V) {
    vi labels(N, 0);
    for(int i = 0; i < N; i++) labels[i] = i;
    cur_labels = labels;

    for(int rep = 0; rep  < 2; rep++) {
        for(int i = 8; i >= 0; i--) {
            int mask = (1 << (i + 1)) - 1;
            for(int j = i - 1; j >= -1; j--) {
                vpi to_sched;

                // cout << bitset<8>(mask) << endl;
                
                for(int k = 0; k < N; k++) {
                    int other = k ^ mask;

                    if(other < N) {
                        pi to_insert = {k, other};
                        
                        if(to_insert.first < to_insert.second) to_sched.pb(to_insert);
                    }
                    
                }
                schedule_and_visit(to_sched);
                if(j >= 0) mask ^= 1 << j;
            }
        }
    }

    for(int i = 0; i < 10; i++) {
        vpi to_sched;
        for(int j = i & 0b1; j < N - 1; j += 2) {
            to_sched.pb({j, j + 1});
        }

        schedule_and_visit(to_sched);
    }

    // if(N >= 3) {
    //     for(int i = 0; i < N; i++) {
    //         int par = (N + i) & 0b1;

    //         vpi to_sched;

    //         for(int j = par; j < N - 1; j += 2) {
    //             to_sched.pb({j, j + 1});
    //         }

    //         schedule_and_visit(to_sched);
    //     }
    // } else if(N == 2) {
    //     schedule_and_visit({{0, 1}});
    // }

    vi ans(N, 0);

    for(int i = 0; i < N; i++) ans[i] = cur_labels[i] + 1;

    answer(ans);
}

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