Submission #970458

#	Time	Username	Problem	Language	Result	Execution time	Memory
970458		jamesbamber	Mechanical Doll (IOI18_doll)	C++17	64.61 / 100	94 ms	9324 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    int source = -N-1;
    vector<int> C(M + 1);
    for(int &x: C) x = source;


    int sz = 0;
    while((1<<sz) <= N) sz++;
    vector<int> X(N+sz), Y(N+sz);
    auto buildtree = [&](int len, int shift){
        vector<pair<int,int>> res(len-1);

        for(int i=0; i<len/2-1; i++) res[i] = {shift - (2*i+1), shift - (2*i+2)};
        for(int i=len/2-1; i<len-1; i++) res[i] = {M+1, M+1};

        return res;
    };

    int curr = -1;
    for(int i=0; i<sz; i++){
        Y[N+i] = -N-i-2;
        if((N & (1 << (sz-i-1))) == 0) X[N+i] = source;
        else{
            if(sz-i-1 == 0){
                X[N+i] = M+1;
            }
            else{
                X[N+i] = curr;
                auto tree = buildtree((1<<(sz-i-1)), curr);
                for(auto [a, b]: tree) X[-curr-1] = a, Y[-curr-1] = b, curr--;
            }
        }
    }
    Y[N+sz-1] = 0;

    vector<int> state(N+sz);
    function<void(int, int)> findnext = [&](int v, int id){
        int u = -v-1;
        assert(v < 0); 
        int next = state[u]?Y[u]:X[u];
        if(next == M+1){
            if(state[u]) Y[u] = id;
            else X[u] = id;
            state[u] ^= 1;
            return;
        }
        state[u] ^= 1;
        findnext(next, id);
    };

    for(int i=0; i<N; i++){
        findnext(source, A[i]);
    }


    //assert(accumulate(state.begin(), state.end(), 0) == 0);

    answer(C, X, Y);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 15.7161781332 / 18
• Subtask 6: 48.8947764144 / 56