#include "doll.h"
#include <bits/stdc++.h>
#define fore(i, b, e) for (int i = b; i < (int)e; ++i)
#define pb push_back
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> ii;
vector<vi> G;
vi leafs;
map<int, int> leafNo;
void genGraph(int lvl, int maxLvl) {
if (lvl == maxLvl) return;
G.pb(vi());
int v = G.size()-1;
if (lvl+1 != maxLvl) {
// X
G[v].pb(G.size());
genGraph(lvl+1, maxLvl);
// Y
G[v].pb(G.size());
genGraph(lvl+1, maxLvl);
}
else {
leafs.pb(v);
}
}
vi order;
void genOrder(vi &vals) {
if (vals.size() == 1) {
order.pb(vals.back());
return;
}
vi L, R;
fore(i, 0, vals.size()) {
if (i&1) R.pb( vals[i] );
else L.pb( vals[i] );
}
genOrder(L);
genOrder(R);
}
vector<bool> isActive;
void delSwitches(int v) {
if (G[v].size() == 0) {
return;
}
delSwitches(G[v][0]);
delSwitches(G[v][1]);
if (isActive[G[v][0]] || isActive[G[v][1]]) isActive[v] = true;
else isActive[v] = false;
}
map<int, ii> switchDirs;
void genAnswer(int v, int curS, int &S) {
if (!isActive[v] || G[v].size() == 0) return;
int L = G[v][0];
int R = G[v][1];
int xS = -1, yS = -1;
if (!isActive[L]) {
xS = -1;
}
else {
if (leafNo.count(L)) xS = leafNo[L];
else xS = --S;
}
if (leafNo.count(R)) yS = leafNo[R];
else yS = --S;
switchDirs[curS] = {xS, yS};
genAnswer(L, xS, S);
genAnswer(R, yS, S);
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
std::vector<int> C;
std::vector<int> X, Y;
if (N == 1) {
C.pb(A[0]);
fore(i, 0, M) C.pb(0);
answer(C, X, Y);
return;
}
A.pb(0);
N++;
int pot = 0, base = 1;
while (base < N) {
base <<= 1;
pot++;
}
genGraph(0, pot+1); // las hojas son los cuadrados
vi vals;
fore(i, 0, base) vals.pb(i);
genOrder(vals);
vi nxt(base, -1), invP(base);
fore(i, 0, base) {
invP[order[i]] = i;
leafNo[leafs[i]] = order[i];
}
for (int i = base-2; i >= 0; i--) {
nxt[i] = invP[i+1];
}
isActive.assign(G.size(), false);
for (int i = base-1, j = 0; j < N; j++, i--) {
isActive[leafs[i]] = true;
}
delSwitches(0);
int accDel = 0;
fore(i, 0, base) {
int leaf = leafs[invP[i]];
if (!isActive[leaf]) accDel++;
else leafNo[leaf] = A[ leafNo[leaf] - accDel ];
}
fore(i, 0, M+1) C.pb(-1);
int S = -1;
genAnswer(0, -1, S);
for (int i = -1; i >= S; --i) {
assert( switchDirs.count(i) == 1 );
X.pb(switchDirs[i].first);
Y.pb(switchDirs[i].second);
}
answer(C, X, Y);
}
