Submission #75239

#	Time	Username	Problem	Language	Result	Execution time	Memory
75239		mammamia	Mechanical Doll (IOI18_doll)	C++14	100 / 100	160 ms	11612 KiB

doll

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

int tokill, swcnt;
bool state[400555];
vector<int> X(400555), Y(400555);

void build(int root, int height, bool orientation){

    //cout<<root<<" "<<orientation<<" "<<(1<<height)<<" \n";
    if((1<<height) <= tokill){
        tokill-= (1<<height);
        X[root-1] = -1;
        return;
    }

    if(height == 0) {
        return;
    }

    swcnt++;
    if (!orientation) {
        X[root - 1] = -swcnt;
    } else {
        Y[root - 1] = -swcnt;
    }
    int aux = swcnt;
    build(aux, height - 1, 0);
    build(aux, height - 1, 1);

}

int nextElement;

void dfs(int root){
    if(!state[(-root)-1]){
        // X
        state[-root-1] = !state[-root-1];
        if(X[-root-1] >= 0){
            X[-root-1] = nextElement;
        } else {
            dfs(X[-root-1]);
        }
    }else{
        state[-root-1] = !state[-root-1];
        if(Y[-root-1] >= 0){
            Y[-root-1] = nextElement;
        } else {
            dfs(Y[-root-1]);
        }
    }
}

void create_circuit(int M, vector<int> A) {

    int N = A.size();
    A.push_back(0);


    int height = 0;
    int aux = N+1;
    while((1<<(height)) < aux){
        height++;
    }

    //cout<<height<<"\n";
    // exits to kill
    tokill = (1<<height) - (N+1);
    //cout<<"tokill "<<tokill<<"\n";
    swcnt = 1;

    build(1, height-1, 0);
    build(1, height-1, 1);
    vector<int> C (M+1);

    for(int i=0; i<=M; ++i){
        C[i] = -1;
    }

    for(int i=0; i<N+1; ++i){
        nextElement = A[i];
        dfs(-1);
    }

    X.resize(swcnt);
    Y.resize(swcnt);

    /*
    for(auto el: C){
        cout<<el<<" ";
    }
    cout<<"\n";
    for(auto el: X){
        cout<<el<<" ";
    }
    cout<<"\n";
    for(auto el: Y){
        cout<<el<<" ";
    }
    cout<<"\n";
     */
    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