#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
// We'll use these to keep track of switch states and IDs
int switch_count = 0;
vector<int> L, R;
vector<bool> state; // false = X, true = Y
// 1. Function to build a perfect binary tree of a certain height
int build_tree(int height) {
if (height == 0) return -1000000; // Placeholder for a leaf
int cur = --switch_count;
L.push_back(0); // Placeholder for child
R.push_back(0); // Placeholder for child
state.push_back(false);
int idx = -cur - 1;
int left_child = build_tree(height - 1);
int right_child = build_tree(height - 1);
L[idx] = left_child;
R[idx] = right_child;
return cur;
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
// Find the smallest power of 2 >= N
int K = 1, H = 0;
while (K < N) { K <<= 1; H++; }
// Initialize our switch tracking
switch_count = 0;
L.clear(); R.clear(); state.clear();
// Build the perfect tree
build_tree(H);
// 2. The "Dry Run"
// We simulate the ball K times.
// The first (K-N) times the ball lands on a leaf, we point it to the root (-1).
// The next N-1 times, we point it to Trigger 1.
// The very last time, we point it to 0.
vector<int*> leaf_pointers;
for (int i = 0; i < K; i++) {
int cur = -1; // Start at root
while (true) {
int idx = -cur - 1;
if (!state[idx]) {
state[idx] = true; // Toggle to Y
if (L[idx] == -1000000) {
leaf_pointers.push_back(&L[idx]);
break;
}
cur = L[idx];
} else {
state[idx] = false; // Toggle to X
if (R[idx] == -1000000) {
leaf_pointers.push_back(&R[idx]);
break;
}
cur = R[idx];
}
}
}
// 3. Connect the leaves in the order they were visited
int skip = K - N;
for (int i = 0; i < K; i++) {
if (i < skip) {
*leaf_pointers[i] = -1; // Send back to root
} else if (i < K - 1) {
*leaf_pointers[i] = 1; // Send to Trigger 1
} else {
*leaf_pointers[i] = 0; // Final trip: Send to Origin
}
}
// Setup Trigger 0 and Trigger 1
vector<int> C(M + 1);
C[0] = 1; // Origin to Trigger 1
C[1] = -1; // Trigger 1 to Root Switch
answer(C, L, R);
}
