Submission #1190771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190771		DanielPr8	The Collection Game (BOI21_swaps)	C++20	5 / 100	7 ms	484 KiB

swaps

#include <bits/stdc++.h>
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;

#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

#include "swaps.h"
/*void __attribute__((noreturn)) __attribute__((format(printf, 1, 2))) result(const char *msg, ...) {
    va_list args;
    va_start(args, msg);
    vfprintf(stderr, msg, args);
    fprintf(stderr, "\n");
    va_end(args);
    exit(0);
}

namespace {
    int N, V, visits;
    set<int> queryIndices;
    vector<int> A, queryResult;
}

void schedule(int i, int j) {
    printf("schedule(%d, %d)\n", i, j);
    fflush(stdout);

    if (i < 1 || i > N || j < 1 || j > N || i == j)
        result("Invalid schedule");
    if (queryIndices.find(i) != queryIndices.end() || queryIndices.find(j) != queryIndices.end())
        result("Invalid schedule");
    queryIndices.insert(i);
    queryIndices.insert(j);

    int s;
    if (scanf("%d", &s) != 1 || (s != 0 && s != 1))
        result("Invalid input");
    if (s)
        swap(A[i], A[j]);
    queryResult.push_back(A[i] < A[j]);
}

vector<int> visit() {
    printf("visit(): {");
    for (int i = 0; i < (int)queryResult.size(); i++) {
        printf("%d", queryResult[i]);
        if (i + 1 != (int)queryResult.size())
            printf(", ");
    }
    printf("}\n");
    fflush(stdout);

    visits++;
    if (visits > V)
        result("Out of visits");

    vector<int> res = queryResult;
    queryIndices.clear();
    queryResult.clear();
    return res;
}

void answer(vector<int> r) {
    printf("answer({");
    for (int i = 0; i < (int)r.size(); i++) {
        printf("%d", r[i]);
        if (i + 1 != (int)r.size())
            printf(", ");
    }
    printf("})\n");

    if ((int)r.size() != N)
        result("Invalid answer");

    for (int i = 0; i < N; i++) {
        if (r[i] < 1 || r[i] > N)
            result("Invalid answer");
        if (A[r[i]] != i + 1)
            result("Wrong answer");
    }

    result("Correct: %d visit(s) used", visits);
}*/

vvl calc(vpl ran){
    if(ran.empty())return {};
    ll n = ran.size();
    vpl ran2;
    for(ll i = 0; i < n; ++i){
        auto [a,b]=ran[i];
        if(a+1<b){
            ran2.pb({a, (a+b)/2});
            ran2.pb({(a+b)/2, b});
        }
    }
    vvl ret = calc(ran2);
    vvl ans(n);
    vector<pair<vll,vll>> sd(n, {{},{}});
    ll j=0;
    for(ll i = n-1; i >= 0; --i){
        auto [a,b]=ran[i];
        if(a+1<b){
            sd[i].f=ret.back();
            ret.pop_back();
            sd[i].s=ret.back();
            ret.pop_back();
        }
        else{
            ans[i]={a};
            j++;
        }
    }
    ll cnt;
    for(;j < n;){
        cnt=0;
        for(ll i = 0; i < n; ++i){
            if(sd[i].f.size()>0 && sd[i].s.size()>0){
                cnt++;
                schedule(sd[i].f.back(), sd[i].s.back());
            }
            else if(sd[i].f.size()+sd[i].s.size()>0){
                ++j;
                while(sd[i].f.size()>0){
                    ans[i].pb(sd[i].f.back());
                    sd[i].f.pop_back();
                }
                while(sd[i].s.size()>0){
                    ans[i].pb(sd[i].s.back());
                    sd[i].s.pop_back();
                }
            }
        }
        if(cnt==0)continue;
        vll pr = visit();
        for(ll i = n-1; i >= 0; --i){
            if(sd[i].f.size()>0 && sd[i].s.size()>0){
                if(pr.back()==0){
                    ans[i].pb(sd[i].f.back());
                    sd[i].f.pop_back();
                }
                else{
                    ans[i].pb(sd[i].s.back());
                    sd[i].s.pop_back();
                }
                pr.pop_back();
            }
        }
        cnt=0;
        for(ll i = 0; i < n; ++i){
            if(sd[i].f.size()>1){schedule(sd[i].f[sd[i].f.size()-1], sd[i].f[sd[i].f.size()-2]);cnt++;}
            if(sd[i].s.size()>1){schedule(sd[i].s[sd[i].s.size()-1], sd[i].s[sd[i].s.size()-2]);cnt++;}
        }
        if(cnt==0)continue;
        vll qr = visit();
        for(ll i = n-1; i >= 0; --i){
            if(sd[i].s.size()>1){
                if(qr.back()==1)swap(sd[i].s[sd[i].s.size()-1], sd[i].s[sd[i].s.size()-2]);
                qr.pop_back();
            }

            if(sd[i].f.size()>1){
                if(qr.back()==1)swap(sd[i].f[sd[i].f.size()-1], sd[i].f[sd[i].f.size()-2]);
                qr.pop_back();
            }
        }
    }
    for(ll i = 0; i < n; ++i)reverse(all(ans[i]));
    return ans;
}

void solve(int n, int v){
    answer(calc({{1,n+1}})[0]);
}

/*int main() {
    if(scanf("%d %d", &N, &V) != 2 || N < 1 || V < 0)
        result("Invalid input");
    A.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        int x;
        if (scanf("%d", &x) != 1 || x < 1 || x > N || A[x])
            result("Invalid input");
        A[x] = i;
    }

    solve(N, V);

    result("No answer");
}*/

• 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