#include "doll.h"
#include <iostream>
#include <algorithm>
using namespace std;
bool used[400000];
int map[400000];
void print_tree(int i, int indent, vector<int> &X, vector<int> &Y) {
if (i >= X.size()) return;
cerr << string(indent*2, ' ') << -i << ": x = " << X[i-1] << " y = " << Y[i-1] << " used = " << used[i-1] << endl;
print_tree(i*2, indent+1, X, Y);
print_tree(i*2+1, indent+1, X, Y);
}
int get_num(int i, int d, int acc) {
if (d == 0) return acc;
return get_num(i / 2, d-1, acc*2 + i%2);
}
void create_circuit(int M, vector<int> A) {
vector<int> C(M + 1, -1);
C[0] = A[0];
int n = A.size();
if (n == 1) {
C[A[0]] = 0;
answer(C, {}, {});
return;
}
A.push_back(0);
A.erase(A.begin());
int N = 1;
int d = 0;
while (N < n) {
N *= 2;
d++;
}
int skip = N - n;
vector<int> X(N, -1), Y(N, -1);
for (int i = 1; i < N/2; i++) {
X[i-1] = -i*2;
Y[i-1] = -i*2 - 1;
}
vector<pair<int, int>> order;
for (int i = skip; i < N; i++) {
used[N/2 - 1 + i/2] = true;
order.push_back({get_num(i, d, 0), i});
}
sort(order.begin(), order.end());
for (int i = skip; i < N; i++) {
int j = order[i - skip].second;
int path = A[i - skip];
if (j % 2 == 0)
X[N/2 - 1 + j/2] = path;
else
Y[N/2 - 1 + j/2] = path;
}
for (int i = N/2-1; i > 0; i--)
used[i-1] = used[i*2-1] || used[i*2];
int map_count = 0;
for (int i = 0; i < N; i++) {
if (used[i]) {
map[i] = -map_count-1;
map_count++;
}
else {
map[i] = -1;
}
}
vector<int> X2(map_count), Y2(map_count);
int mapi = 0;
for (int i = 0; i < N; i++) {
if (used[i]) {
X2[mapi] = X[i] < 0 ? map[-X[i]-1] : X[i];
Y2[mapi] = Y[i] < 0 ? map[-Y[i]-1] : Y[i];
mapi++;
}
}
print_tree(1, 0, X, Y);
answer(C, X2, Y2);
}
