IOI18: Mechanical Doll

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

vector<int> X(0), Y(0);

int seq = 0;
int createSwitch(int x, int y){
    X.push_back(x);
    Y.push_back(y);
    --seq;
    return seq;
}

int createTree(vector<int> &V){
    int n = V.size();
    if(n == 1){
        return V[0];
    }
    bool same = true;
    for(int i = 0; i < n - 1; ++i){
        if(V[i] != V[i + 1]){
            same = false;
            break;
        }
    }
    if(same){
        return V[0];
    }
    vector<int> x(0), y(0);
    for(int i = 0; i < n; ++i){
        if(i % 2 == 0){
            x.push_back(V[i]);
        } else {
            y.push_back(V[i]);
        }
    }
    int ix = createTree(x);
    int iy = createTree(y);
    return createSwitch(ix, iy);
}

int revBit(int a, int k){
    int b = 0;
    while(k--){
        b <<= 1;
        b |= (a & 1);
        a >>= 1;
    }
    return b;
}

void create_circuit(int M, vector<int> A){
    int n = A.size();
    int nExp = 0;
    while((1 << nExp) < n){
        ++nExp;
    }
    A.push_back(0);
    vector<int> V(1 << nExp, 0);
    for(int i = 0; i < (1 << nExp) - n; ++i){
        V[revBit(i, nExp)] = 1e9;
    }
    int idx = 1;
    for(int i = 0; i < (1 << nExp); ++i){
        if(V[i] != 0){
            continue;
        }
        V[i] = A[idx];
        ++idx;
    }
    int root = createTree(V);

    vector<int> C(M + 1, root);
    C[0] = A[0];
    for(auto &x : X){
        if(x == 1e9){
            x = root;
        }
    }
    for(auto &y : Y){
        if(y == 1e9){
            y = root;
        }
    }

    answer(C, X, Y);
}