Submission #1366317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1366317		Sofiatpc	The Collection Game (BOI21_swaps)	C++20	5 / 100	3 ms	468 KiB

swaps

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

using namespace std;

#define sz(v) (int)v.size()

void solve(int n, int V) {
    vector< vector<int> > v[2];
    for(int i = 1; i <= n; i++)v[0].push_back({i});

    int cur = 0;
    while(sz(v[cur]) > 1){
        int qtd = 0;
        vector<int> e,d;
        for(int i = 0; i+1 < sz(v[cur]); i+=2){
            qtd = max(qtd, sz(v[cur][i]) + sz(v[cur][i+1]) );
            e.push_back(0); d.push_back(0);
        }

        v[cur^1].resize( (sz(v[cur])+1)/2 );
        if(sz(v[cur])%2 == 1){
            for(int x : v[cur].back() ) v[cur^1][ sz(v[cur^1])-1 ].push_back(x);
        }

        while(qtd--){
            int ask = 0;
            for(int i = 0; i+1 < sz(v[cur]); i+=2){
                if(e[i/2] < sz(v[cur][i]) && d[i/2] < sz(v[cur][i+1]) ){
                    schedule( v[cur][i][e[i/2]], v[cur][i+1][d[i/2]]);
                    ask = 1;
                }else if(e[i/2] < sz(v[cur][i])){
                    v[cur^1][i/2].push_back( v[cur][i][ e[i/2] ] );
                    e[i/2]++;
                }else if(d[i/2] < sz(v[cur][i+1])){
                    v[cur^1][i/2].push_back( v[cur][i+1][ d[i/2] ] );
                    d[i/2]++;
                }
            }

            if(!ask)continue;

            vector<int> resp = visit();
            int pt = 0;
            for(int i = 0; i+1 < sz(v[cur]); i+=2){
                if(e[i/2] < sz(v[cur][i]) && d[i/2] < sz(v[cur][i+1]) ){
                    if(resp[pt]){
                        v[cur^1][i/2].push_back( v[cur][i][ e[i/2] ] );
                        e[i/2]++;
                    }else{
                        v[cur^1][i/2].push_back( v[cur][i+1][ d[i/2] ] );
                        d[i/2]++;
                    }
                    pt++;
                }
            }
        }

        v[cur].clear(); cur ^= 1;
    }

    answer(v[cur][0]);
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3-1: 0 / 3
• Subtask 3-2: 0 / 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