Submission #970397

#	Time	Username	Problem	Language	Result	Execution time	Memory
970397		jamesbamber	Mechanical Doll (IOI18_doll)	C++17	37 / 100	142 ms	13136 KiB

doll

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

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    vector<int> C(M + 1);

    int sz = 1;
    while(sz <= N) sz*= 2;

    vector<int> state(sz+1);
    vector<int> id(2*sz+2);

    function<void(int,int)> addid = [&](int v, int i){
        if(v >= sz){
            id[v] = i;
            return;
        }
        else id[v] = -v;

        addid(2*v + state[v], i);
        state[v] ^= 1;
    };

    for(int i=0; i<N; i++) addid(1, A[i]);
    for(int i=N; i<sz-1; i++) addid(1, -1);
    addid(1, 0);

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

    vector<int> X(sz), Y(sz);
    for(int &x: C) x = -1;
    for(int i=1; i<=sz; i++){
        X[i-1] = id[2*i];
        Y[i-1] = id[2*i+1];
    }

    // for(int x: C) cout << x << " "; cout << endl;
    // for(int x: X) cout << x << " "; cout << endl;
    // for(int x: Y) cout << x << " "; cout << endl;


    answer(C, X, Y);
}

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