#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
bool isbackloop(int index, int switchsize, int backloopcount) {
if(backloopcount == switchsize)
return true;
if(backloopcount == 0)
return false;
int abackloops = min((int)switchsize / 2, backloopcount), bbackloops = backloopcount - abackloops;
if(index % 2 == 0)
return isbackloop(index / 2, switchsize / 2, abackloops);
return isbackloop(index/2, switchsize / 2, bbackloops);
}
int makeswitch(vi &outs, vi &x, vi &y, int backloops = -1, int backloopswitch = 0, int switchsize = 0)
{
if(backloops == switchsize)
return backloopswitch;
if(switchsize == 1)
return outs[0];
int switchindex = -x.size() - 1;
x.push_back(0);
y.push_back(0);
int size = outs.size();
if(backloops == -1)
{
size = __bit_ceil(outs.size());
backloops = size - outs.size();
switchsize = size;
backloopswitch = switchindex;
}
vi a, b;
int abackloops = min((int)switchsize / 2, backloops), bbackloops = backloops - abackloops;
queue<int> q;
for(auto i: outs)
q.push(i);
for(int i = 0; i < switchsize; i += 2)
{
if(!isbackloop(i/2, switchsize/2, abackloops))
{
a.push_back(q.front()); q.pop();
}
if(!isbackloop(i/2, switchsize/2, bbackloops))
{
b.push_back(q.front()); q.pop();
}
}
x[-switchindex-1] = makeswitch(a, x, y, abackloops, backloopswitch, switchsize/2);
y[-switchindex-1] = makeswitch(b, x, y, bbackloops, backloopswitch, switchsize/2);
return switchindex;
}
void create_circuit(int m, vi a) {
int n = a.size();
vvi next(m+1);
next[0].push_back(a[0]);
for(int i = 1; i < n; i++)
{
next[a[i-1]].push_back(a[i]);/* */
}
next[a[n-1]].push_back(0);
vi c(m+1), x, y;
for(int i = 0; i < m + 1; i++)
{
if(next[i].empty())
continue;
c[i] = makeswitch(next[i], x, y, -1, 0, next[i].size());
}
answer(c, x, y);
}
