#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int START_SENTINEL = 0xdeadbeef;
const int ROOT_SENTINEL = 0x15571557;
void create_circuit(int m, vector<int> a) {
int n = a.size();
vector<int> x, y;
auto add_switch = [&](int sx, int sy) {
x.push_back(sx);
y.push_back(sy);
return -x.size();
};
// returns root
function<int(int, int, int)> construct_t_pow = [&](int sz, int off,
int stride) -> int {
if (sz == 1) {
return off;
} else {
int l = construct_t_pow(sz / 2, off, 2 * stride);
int r = construct_t_pow(sz / 2, off + stride, 2 * stride);
return add_switch(l, r);
}
};
function<int(int, int, int, int)> construct_t = [&](int sz, int csz, int off,
int stride) -> int {
if (csz == sz) {
return construct_t_pow(csz, off, stride);
}
if (csz == 1 && sz == 0) return 0; // the zero-node
if ((csz / 2) & sz) {
int l = construct_t_pow(csz / 2, off, 2 * stride);
int r = construct_t(sz - (csz / 2), csz / 2, off + stride, 2 * stride);
return add_switch(l, r);
} else {
int l = ROOT_SENTINEL; // the root
int r = construct_t(sz, csz / 2, off + stride, 2 * stride);
return add_switch(l, r);
}
};
int csz = 2 << __lg(n);
int root = construct_t(n, csz, 1, 1);
vector<int> indices;
for (int i = 0; i < x.size(); ++i) {
if (x[i] == ROOT_SENTINEL) x[i] = root;
if (y[i] == ROOT_SENTINEL) y[i] = root;
if (x[i] > 0) indices.push_back(x[i]);
if (y[i] > 0) indices.push_back(y[i]);
}
sort(indices.begin(), indices.end());
for (int i = 0; i < x.size(); ++i) {
if (x[i] > 0)
x[i] = a[lower_bound(indices.begin(), indices.end(), x[i]) -
indices.begin()];
if (y[i] > 0)
y[i] = a[lower_bound(indices.begin(), indices.end(), y[i]) -
indices.begin()];
}
answer(vector<int>(m + 1, root), x, y);
return;
}
#ifndef EVAL
#include "grader.cpp"
#endif
