#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> exitFixed;
vector<int> exitEven, exitOdd;
int nbSwaps;
bool allRoot(vector<int> e) {
for (auto v : e)
if (v != -1)
return false;
return true;
}
int build(vector<int> elements) {
int nbElem = elements.size();
assert(nbElem > 1);
if (nbElem == 2) {
++nbSwaps;
exitEven.push_back(elements[0]);
exitOdd.push_back(elements[1]);
return -nbSwaps;
}
vector<int> even, odd;
for (int i = 0; i < nbElem; ++i)
(i % 2 ? odd : even).push_back(elements[i]);
int ret = ++nbSwaps;
exitEven.push_back(-1e9);
exitOdd.push_back(-1e9);
if (allRoot(even))
exitEven[ret - 1] = -1;
else
exitEven[ret - 1] = build(even);
if (allRoot(odd))
exitOdd[ret - 1] = -1;
else if (odd.size() > 1)
exitOdd[ret - 1] = build(odd);
else
exitOdd[ret - 1] = odd.back();
return -ret;
}
vector<int> posFeuilles(vector<int> restants) {
int nbRestants = restants.size();
assert(__builtin_popcount(nbRestants));
if (nbRestants == 1)
return {restants[0]};
vector<int> even, odd;
for (int i = 0; i < nbRestants; ++i)
(i % 2 ? odd : even).push_back(restants[i]);
auto lft = posFeuilles(even), rgt = posFeuilles(odd);
for (auto v : rgt)
lft.push_back(v);
return lft;
}
void create_circuit(int nbFixes, vector<int> ordre) {
int nbEtapes = ordre.size();
exitFixed.resize(nbFixes + 1);
exitFixed[0] = ordre[0];
if (nbEtapes == 1) {
exitFixed[ordre[0]] = 0;
answer(exitFixed, exitEven, exitOdd);
return;
}
int k = 0;
while ((1LL << (k + 1)) < nbEtapes)
k++;
int restant = (1 << (k + 1)) - nbEtapes;
if ((1 << k) == nbEtapes)
restant = 0;
vector<int> v;
for (int i = 0; i < restant + nbEtapes; ++i)
v.push_back(i);
auto pos = posFeuilles(v);
cerr << "Val : " << k << ' ' << restant << endl;
vector<int> toBuild(restant + nbEtapes);
for (int i = 0; i < restant; ++i)
toBuild[pos[i]] = -1;
vector<int> restantes;
for (int i = restant; i < nbEtapes + restant; ++i)
restantes.push_back(pos[i]);
sort(restantes.begin(), restantes.end());
for (int i = 0; i < nbEtapes; ++i)
toBuild[restantes[i]] = i + 1 < nbEtapes ? ordre[i + 1] : 0;
for (int i = 1; i <= nbFixes; ++i)
exitFixed[i] = -1;
build(toBuild);
cerr << "count switch : " << exitEven.size() << endl;
assert((int)exitEven.size() <= nbEtapes + (int)log2(nbEtapes));
assert(nbSwaps <= 2 * nbEtapes);
answer(exitFixed, exitEven, exitOdd);
}
