Submission #1215146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215146		ProtonDecay314	The Collection Game (BOI21_swaps)	C++20	44 / 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]);
        }
    }
}

int g_N;

void schedule_mask(int mask) {
    vpi to_sched;

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

        if(other < g_N) {
            pi to_insert = {k, other};
            
            if(to_insert.first < to_insert.second) to_sched.pb(to_insert);
        }
        
    }
    schedule_and_visit(to_sched);
}

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

    
    schedule_mask(0b111111111);
    schedule_mask(0b101111111);
    schedule_mask(0b100111111);
    schedule_mask(0b100011111);
    schedule_mask(0b100001111);
    schedule_mask(0b100000111);
    schedule_mask(0b100000011);
    schedule_mask(0b100000001);
    schedule_mask(0b100000000);

    schedule_mask(0b11111111);
    schedule_mask(0b10111111);
    schedule_mask(0b10011111);
    schedule_mask(0b10001111);
    schedule_mask(0b10000111);
    schedule_mask(0b10000011);
    schedule_mask(0b10000001);
    schedule_mask(0b10000000);

    schedule_mask(0b1111111);
    schedule_mask(0b1011111);
    schedule_mask(0b1001111);
    schedule_mask(0b1000111);
    schedule_mask(0b1000011);
    schedule_mask(0b1000001);
    schedule_mask(0b1000000);

    schedule_mask(0b111111);
    schedule_mask(0b101111);
    schedule_mask(0b100111);
    schedule_mask(0b100011);
    schedule_mask(0b100001);
    schedule_mask(0b100000);

    schedule_mask(0b11111);
    schedule_mask(0b10111);
    schedule_mask(0b10011);
    schedule_mask(0b10001);
    schedule_mask(0b10000);

    schedule_mask(0b1111);
    schedule_mask(0b1011);
    schedule_mask(0b1001);
    schedule_mask(0b1000);

    schedule_mask(0b0111);
    schedule_mask(0b0101);
    schedule_mask(0b0100);

    schedule_mask(0b0011);
    schedule_mask(0b0010);
    
    schedule_mask(0b0001);

    schedule_mask(0b111111111);
    schedule_mask(0b11111111);
    schedule_mask(0b1111111);
    schedule_mask(0b111111);
    schedule_mask(0b11111);
    schedule_mask(0b01111);
    schedule_mask(0b00111);
    schedule_mask(0b00011);
    schedule_mask(0b00001);

    schedule_mask(0b111111111);
    schedule_mask(0b11111111);
    schedule_mask(0b1111111);
    schedule_mask(0b111111);
    schedule_mask(0b11111);
    schedule_mask(0b01111);
    schedule_mask(0b00111);
    schedule_mask(0b00011);
    schedule_mask(0b00001);

    schedule_mask(0b111111111);
    schedule_mask(0b11111111);
    schedule_mask(0b1111111);
    schedule_mask(0b111111);
    schedule_mask(0b11111);
    schedule_mask(0b01111);
    schedule_mask(0b00111);
    schedule_mask(0b00011);
    schedule_mask(0b00001);

    schedule_mask(0b111111111);
    schedule_mask(0b11111111);
    schedule_mask(0b1111111);
    schedule_mask(0b111111);
    schedule_mask(0b11111);
    schedule_mask(0b01111);
    schedule_mask(0b00111);
    schedule_mask(0b00011);
    schedule_mask(0b00001);

    schedule_mask(0b111111111);
    schedule_mask(0b11111111);
    schedule_mask(0b1111111);
    schedule_mask(0b111111);
    schedule_mask(0b11111);
    schedule_mask(0b01111);
    schedule_mask(0b00111);
    schedule_mask(0b00011);
    schedule_mask(0b00001);

    schedule_mask(0b111111111);
    schedule_mask(0b11111111);
    schedule_mask(0b1111111);
    schedule_mask(0b111111);
    schedule_mask(0b11111);
    schedule_mask(0b01111);
    schedule_mask(0b00111);
    schedule_mask(0b00011);
    schedule_mask(0b00001);

    // schedule_mask(0b111111);
    // schedule_mask(0b11111);
    // schedule_mask(0b01111);
    // schedule_mask(0b00111);
    // schedule_mask(0b00011);
    // schedule_mask(0b00001);

    

    // 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: 9 / 9
• Subtask 4-2: 6 / 6
• Subtask 5-1: 9 / 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