#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> C;
vector<int> X;
vector<int> Y;
int switch_counter = 0;
int nsw() {
X.push_back(0);
Y.push_back(0);
return -(++switch_counter);
}
int br(size_t start_idx, size_t count, int kill_dest, const vector<int>& dests) {
if (count == 1) {
if (start_idx < dests.size()) {
return dests[start_idx];
}
else {
return kill_dest;
}
}
int csw = nsw();
size_t half = count / 2;
int lc = br(start_idx, half, kill_dest, dests);
int rc = br(start_idx + half, half, kill_dest, dests);
X[-csw - 1] = lc;
Y[-csw - 1] = rc;
return csw;
}
int cms(const vector<int>& dests) {
size_t k = dests.size();
if (k == 0) return 0;
if (k == 1) return dests[0];
size_t m = 1;
while (m < k) {
m *= 2;
}
int rsw = nsw();
size_t half = m / 2;
int lc = br(0, half, rsw, dests);
int rc = br(half, half, rsw, dests);
X[-rsw - 1] = lc;
Y[-rsw - 1] = rc;
return rsw;
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
C.assign(M + 1, 0);
vector<int> destinations = A;
destinations.push_back(0);
size_t k = destinations.size();
if (k == 1) {
answer(C, X, Y);
return;
}
int master_root = cms(destinations);
C[0] = master_root;
vector<bool> is_trigger_used(M + 1, false);
for (int trigger_id : A) {
if (trigger_id > 0 && trigger_id <= M) {
is_trigger_used[trigger_id] = true;
}
}
for (int t = 1; t <= M; ++t) {
if (is_trigger_used[t]) {
C[t] = master_root;
}
}
answer(C, X, Y);
}
