제출 #970462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970462		jamesbamber	자동 인형 (IOI18_doll)	C++17	100 / 100	101 ms	10124 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 = -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 = -sz-1;
    for(int i=0; i<sz; i++){
        Y[i] = -i-2;
        if((N & (1 << (sz-i-1))) == 0) X[i] = source;
        else{
            if(sz-i-1 == 0){
                X[i] = M+1;
            }
            else{
                X[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[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]);
    }

    X.resize(-curr-1);
    Y.resize(-curr-1);
    //assert(accumulate(state.begin(), state.end(), 0) == 0);

    answer(C, X, Y);
}

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