#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;
if (nbElem % 2) {
odd.push_back(even.back());
even.back() = -ret;
}
assert((int)odd.size() < nbElem);
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;
}
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;
cerr << "Val : " << k << ' ' << restant << endl;
vector<int> toBuild;
while (restant--)
toBuild.push_back(-1);
for (int i = 0; i < nbEtapes; ++i)
toBuild.push_back(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);
}
