#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
struct Switch
{
bool state;
Switch *l,*r;
int lv=-1,rv=-1;
int num=0;
};
Switch *create_tree(int li,int ri)
{
Switch* a = new Switch();
a->state = false;
if(ri-li > 2)
{
int m = (li+ri)>>1;
a->l = create_tree(li,m);
a->r = create_tree(m,ri);
}
else
{
a->l = nullptr;
a->r = nullptr;
}
return a;
}
int& traverse(Switch* root)
{
if(root->state)
{
root->state = false;
if(root->r) return traverse(root->r);
return root->rv;
}
else
{
root->state = true;
if(root->l) return traverse(root->l);
return root->lv;
}
}
void prune(Switch *root,int b, int l,int r,Switch *here=nullptr)
{
if(here==nullptr) here = root;
if(l==b) return;
int m = (l+r)/2;
if (m <= b)
{
here->l = root;
if(m==b) return;
prune(root,b,m,r,here->r);
}
else prune(root,b,l,m,here->l);
}
vector<Switch*> switches;
int enumerate(Switch *here)
{
static int i = 0;
if(here == nullptr || here->num != 0) return -i;
switches.push_back(here);
here->num = --i;
enumerate(here->l);
enumerate(here->r);
return -i;
}
void assign(Switch *here,vector<int>& X, vector<int>& Y)
{
static set<Switch*> seen;
if(seen.count(here)) return;
seen.insert(here);
if(!here) return;
if(!here->num) return;
if(here->l)
{
X[-here->num-1] = here->l->num;
}
else
{
X[-here->num-1] = here->lv;
}
if(here->r)
Y[-here->num-1] = here->r->num;
else
Y[-here->num-1] = here->rv;
assign(here->l,X,Y);
assign(here->r,X,Y);
}
Switch* root;
void printTree(Switch* here,string prev = "", string out = "└─",string follow = " ")
{
return;
if(here==nullptr) {cout << prev << out << "\n"; return;}
cout << prev << out << here->num << " " << here->lv << " " << here->rv << " " << here->state << "\n";
if(here->l == root)
cout << prev << follow << "├─root\n";
else if(here->l)
printTree(here->l,prev+follow,"├─","│ ");
if(here->r == root)
cout << prev << follow << "└─root\n";
else if(here->r)
printTree(here->r,prev+follow,"└─"," ");
}
void set_neg2_root(Switch* here, Switch* root)
{
if (here->lv==-2) here->l = root;
else if (here->l!=root && here->l) set_neg2_root(here->l,root);
if (here->rv==-2) here->r = root;
else if (here->r!=root && here->r) set_neg2_root(here->r,root);
}
int log2(int a)
{
int i = 0;
for(;(1<<i)<a;i++);
return i;
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
int Nru = 1 << (log2(N+1));
A.push_back(0);
root = create_tree(0,Nru);
printTree(root);
prune(root,Nru-N-1,0,Nru);
printTree(root);
int num_switches = enumerate(root);
printTree(root);
vector<int> C(M+1),X(num_switches),Y(num_switches);
for(auto i : A) traverse(root) = i;
set_neg2_root(root,root);
printTree(root);
for(auto&& i : C) i = -1;
assign(root,X,Y);
answer(C, X, Y);
}
