#include "doll.h"
#include <cstdio>
using namespace std;
vector<int> c;
vector<int> xs;
vector<int> ys;
vector<int> a;
int ai = 0;
int n = 0;
struct Switch;
extern Switch* switches;
int add_switch(Switch);
int not_used = 0;
struct Switch {
int x;
int y;
int state;
void gen_childs(int num, int remaining) {
//printf("%d %d\n", num, remaining);
//printf("s: %d\n", num);
if (num <= 2) {
x = 0;
y = 0;
ys.push_back(0);
xs.push_back(0);
not_used += 2;
return;
}
/*if (num == 3) {
Switch s = Switch{0, 0, 0};
x = add_switch(s);
xs.push_back(-x);
ys.push_back(0);
switches[x].gen_childs(2);
return;
}*/
Switch s1 = Switch{1, 1, 0};
y = add_switch(s1);
ys.push_back(-y);
int i = xs.size();
xs.push_back(-1);
//printf("t: %d %d\n", x, y);
int a = min(num/2, remaining);
switches[y].gen_childs(num/2, a);
remaining -= a;
if (remaining > 0) {
Switch s2 = Switch{1, 1, 0};
x = add_switch(s2);
xs[i] = -x;
switches[x].gen_childs(num/2, remaining);
}
}
int get() {
int next = x;
if (state == 1) next = y;
state = !state;
return next;
}
};
#define NUM_SWITCHES 1000000
Switch switches2[NUM_SWITCHES];
Switch* switches = switches2;
int index = 1;
int add_switch(Switch s) {
switches[index] = s;
index++;
return index-1;
}
void print_tree() {
printf("X: ");
for (int i = 0; i < int(xs.size()); i++) {
printf("%d, ", xs[i]);
}
printf("\n");
printf("Y: ");
for (int i = 0; i < int(ys.size()); i++) {
printf("%d, ", ys[i]);
}
printf("\n");
}
void sim_switches(int s) {
//print_tree();
//printf("%d\n", s);
int next = switches[s].get();
if (next == 0) {
not_used--;
if (not_used == 0) {
ys[s-1] = 0;
return;
}
next = -1;
if (ai < n) {
next = a[ai];
}
//printf("k: %d %d\n", next, not_used);
if (switches[s].state == 1) {
xs[s-1] = next;
//printf("x: (%d %d)\n", s-1, next);
} else {
ys[s-1] = next;
//printf("x: (%d %d)\n", s-1, next);
}
ai++;
sim_switches(1);
return;
}
sim_switches(next);
}
void create_circuit(int M, std::vector<int> A) {
a = A;
int N = A.size();
n = N;
int s = add_switch(Switch{0,0,0});
int b = 1;
while (b < n+1) {
b *= 2;
}
switches[s].gen_childs(b, n+1);
sim_switches(1);
vector<int> C(M + 1);
C[0] = -1;
for (int i = 1; i <= M; ++i) {
C[i] = -1;
}
//print_tree();
//C[A[N-1]] = 0;
/*
printf("C: ");
for (int i = 0; i <= M; i++) {
printf("%d, ", C[i]);
}
printf("\n");
printf("X: ");
for (int i = 0; i < int(xs.size()); i++) {
printf("%d, ", xs[i]);
}
printf("\n");
printf("Y: ");
for (int i = 0; i < int(ys.size()); i++) {
printf("%d, ", ys[i]);
}
printf("\n");
*/
answer(C, xs, ys);
}
