Submission #894609

#	Time	Username	Problem	Language	Result	Execution time	Memory
894609		esomer	The Collection Game (BOI21_swaps)	C++17	35 / 100	37 ms	1684 KiB

swaps

#include <bits/stdc++.h>
#include "swaps.h"

using namespace std;

mt19937 gen(time(0));

void add(vector<int>& a, vector<pair<vector<int>, vector<int>>>& all){
    int n = (int)a.size();
    int sz = (n + 1) / 2;
    shuffle(a.begin(), a.end(), gen);
    all.push_back({{}, {}});
    for(int i = 0; i < sz; i++) all.back().first.push_back(a[i]);
    for(int i = sz; i < n; i++) all.back().second.push_back(a[i]);
}

void solve(int N, int V) {
    vector<pair<vector<int>, vector<int>>> all;
    int sz = (N+1) / 2;
    vector<int> a(N);
    for(int i = 0; i < N; i++) a[i] = i + 1;
    add(a, all);
    bool stop = false;
    while(!stop){
        int mx = 0;
        for(auto p : all){
            mx = max(mx, (int)p.second.size());
        }
        for(int change = 0; change < mx + 1; change++){
            for(auto& p : all){
                for(int i = 0; i < (int)p.second.size(); i++){
                    schedule(p.second[i], p.first[(i + change) % (int)p.first.size()]);
                }
            }
            vector<int> rep = visit();
            int curr = 0;
            for(auto& p : all){
                for(int i = 0; i < (int)p.second.size(); i++){
                    if(rep[curr] == 1) swap(p.second[i], p.first[(i + change) % (int)p.first.size()]);
                    curr++;
                }
            }
        }
        vector<pair<vector<int>, vector<int>>> nw;
        for(auto p : all){
            add(p.first, nw);
            add(p.second, nw);
        }
        all = nw;
        if(sz == 1) stop = true;
        sz = (sz + 1) / 2;
    }
    vector<int> r;
    for(auto p : all){
        for(int x : p.first) r.push_back(x);
        for(int x : p.second) r.push_back(x);
    }
    answer(r);
}

• 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: 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