#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> exitFixed;
vector<int> exitEven, exitOdd;
int nbSwaps;
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);
exitEven[ret - 1] = build(even);
exitOdd[ret - 1] = build(odd);
return -ret;
}
void create_circuit(int nbFixes, vector<int> ordre) {
int nbEtapes = ordre.size();
vector<vector<int>> goAfter(nbFixes);
for (int i = 0; i < nbEtapes; ++i) {
if (i + 1 < nbEtapes)
goAfter[ordre[i] - 1].push_back(ordre[i + 1]);
else
goAfter[ordre[i] - 1].push_back(0);
}
exitFixed.resize(nbFixes + 1);
vector<int> elem;
for (int i = 0; i < nbEtapes; ++i)
elem.push_back(i + 1 < nbEtapes ? ordre[i + 1] : 0);
exitFixed[0] = ordre[0];
int r = build(elem);
for (int i = 1; i <= nbFixes; ++i)
exitFixed[i] = r;
answer(exitFixed, exitEven, exitOdd);
return;
for (int i = 0; i < nbFixes; ++i) {
if (goAfter[i].empty())
continue;
if (goAfter[i].size() == 1) {
exitFixed[i + 1] = goAfter[i].front();
continue;
}
exitFixed[i + 1] = build(goAfter[i]);
}
answer(exitFixed, exitEven, exitOdd);
}
