/**
* An interesting construction~
* [Tree] It was quite straight-forward (for me) to come up with a tree solution.
* Namely, each trigger's exit should point to a single switch known as the
* "root" of our tree. Our switches form shall form a rooted binary tree, with
* the exits of the leaves pointing back to the triggers, as specified in the
* input order. This idea is best illustrated when N is a power of 2 ([S4]). In
* this case, we assign the exits of the N/2 leaves using the reverse bit order
* of A[]. As a side note, the number of state changes is bounded by
* O(N * log_2(N)), so the limit of P is easily satisfied. (Well, the limit is
* there just for the grader~)
* [Non-perfect tree] Then, I realized that this tree form isn't limited to perfect
* binary trees. Note that the tree can be defined in a recursive way. If a
* switch has to be responsible for N turns, we can create two new subtrees and
* point to them. The X subtree shall be responsible for ceil(N/2) turns, while
* the Y subtree shall be responsible for floor(N/2) turns. However, we quickly
* realize that this is impossible since each switch should return to state X
* when the ball completes a cycle. In the end, it seems that we still have to
* add "turns" that point back to the root of our tree, so we still need
* two_pow - 1 nodes...
* [m=1] We have to create a circuit that passes trigger 1 exactly n times. Let
* two_pow = 2^(ceil(log_2(n))). It's clear that we can use two_pow-1 nodes to
* form a tree, with some leaf's exits pointing to the tree root instead of some
* trigger. But notice sth: some switches are unnecessary. If X and Y point to
* two subtrees which are isomorphic, this switch isn't necessary, so this
* subtask can be solved with log_2(n) switches~
* This idea of shrinking subtrees can be extended to the full solution. We first
* order A[] in a modified version of reverse bit order. We put exits that point back
* to the root "as left as possible" so that the "shrinking" effect can be maximised.
* I know I've done a bad job describing this... Sorry~
*
* Switches needed: n - 1 + #ones_in_binary(two_pow - n),
* two_pow = 2^(ceil(log_2(n)) (bound tight except for const term)
* Implementation 1 (Full solution, construction, binary tree)
*/
#include <bits/stdc++.h>
#include "doll.h"
typedef std::vector<int> vec;
const int INF = 0x3f3f3f3f;
int reverse(int t, int digits) {
int res = 0;
for (int d = 0; d < digits; d++)
res |= (1 << (digits - 1 - d)) * ((t >> d) & 1);
return res;
}
vec order; // reverse bit order / exits for the leaves
vec X, Y;
// The index of the root is returned. *helper* is the num of helper exits.
int build_tree(int l, int r, int helper) {
int m = r - l, mid = (l + r) / 2;
if (m == 1)
return order[l]; // Directly return the node. We don't have to create one.
int x, y;
if (helper >= m / 2)
x = -INF, y = build_tree(mid, r, helper - m / 2); // -INF: placeholder
else
x = build_tree(l, mid, helper), y = build_tree(mid, r, 0);
X.push_back(x);
Y.push_back(y);
return -X.size();
}
void create_circuit(int m, vec A) {
int n = A.size();
A.push_back(0);
int pow = 0, two_pow = 1;
while (two_pow < n)
pow++, two_pow *= 2;
int helpers = two_pow - n;
// reverse bit order, impl inspired by cp-algorithms.com/algebra/fft.html
order.resize(two_pow);
for (int i = 0, j = 1; i < two_pow; i++) {
int rev = reverse(i, pow);
order[rev] = (rev >= helpers ? A[j++] : -INF); // -INF: placeholder for root
}
int tree_root = build_tree(0, two_pow, helpers);
std::replace(X.begin(), X.end(), -INF, tree_root);
std::replace(Y.begin(), Y.end(), -INF, tree_root);
vec C(m + 1, tree_root);
C[0] = A[0];
assert(int(X.size()) == n - 1 + __builtin_popcount(two_pow - n));
answer(C, X, Y);
}
