#include "doll.h"
#include <vector>
#include <cassert>
#include <cstdio>
using namespace std;
namespace TreeSol {
typedef vector<int> VI;
struct Node {
int L, R;
int id;
bool flipped, loop;
Node(int _L = -1, int _R = -1, int _id = 999999)
: L(_L), R(_R), id(_id), flipped(false), loop(false) {}
};
vector<Node> nodes;
int g_num_switches = 0;
void build_tree(int p, int q, int idx, int L, int R) {
if (p > R || q < L) {
nodes[idx] = Node(L, R, nodes[1].id); // root
nodes[idx].loop = true;
return;
}
if (L == R) {
nodes[idx] = Node(L, R);
return;
}
int mid = (L+R)/2;
g_num_switches++;
nodes[idx] = Node(L, R, -g_num_switches);
build_tree(p, q, idx*2, L, mid);
build_tree(p, q, idx*2+1, mid+1, R);
}
void assign_device_id(int id, int idx = 1) {
if (nodes[idx].loop) {
assign_device_id(id, 1);
return;
}
if (nodes[idx].L == nodes[idx].R) {
nodes[idx].id = id;
return;
}
nodes[idx].flipped = !nodes[idx].flipped;
if (nodes[idx].flipped)
assign_device_id(id, 2*idx);
else
assign_device_id(id, 2*idx+1);
}
struct Switch {
int x, y;
};
vector<Switch> switches;
void assign_switch_exits(int idx = 1) {
if (nodes[idx].L < 0) return;
if (nodes[idx].loop) return;
if (nodes[idx].L == nodes[idx].R) return;
assign_switch_exits(idx*2);
assign_switch_exits(idx*2 + 1);
assert(nodes[idx].id < 0);
int switch_id = -(nodes[idx].id+1);
switches[ switch_id ].x = nodes[idx*2 ].id;
switches[ switch_id ].y = nodes[idx*2+1].id;
}
int build_circuit(int src, const VI& nxt) {
int K = nxt.size();
if (K == 1)
return nxt[0];
int nodes_last_level = 1;
while (nodes_last_level < K)
nodes_last_level *= 2;
nodes = vector<Node>(2*nodes_last_level + 1);
/*
if (src == 3) {
fprintf(stderr, "nodes_last_level: %d\n", nodes_last_level);
fprintf(stderr, "p: %d q: %d\n", nodes_last_level-K, nodes_last_level-1);
}
*/
build_tree(nodes_last_level - K, nodes_last_level - 1,
1, 0, nodes_last_level-1);
int ret = nodes[1].id;
for (int dev_id : nxt)
assign_device_id(dev_id);
/*
if (src == 3) {
for (int idx = 1; idx < int(nodes.size()); ++idx) {
Node x = nodes[idx];
fprintf(stderr, "idx:%d L:%d R:%d id:%d loop:%d\n",
idx, x.L, x.R, x.id, x.loop);
}
}
*/
switches.resize(g_num_switches);
assign_switch_exits();
return ret;
}
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
vector< vector<int> > nxt(M+1);
for (int i = 1; i < N; ++i)
nxt[ A[i-1] ].push_back( A[i] );
nxt[ A.back() ].push_back(0);
vector<int> C(M + 1);
C[0] = A[0];
for (int i = 1; i <= M; ++i) {
if (nxt[i].empty()) continue;
C[i] = TreeSol::build_circuit(i, nxt[i]);
}
int S = TreeSol::switches.size();
vector<int> X(S), Y(S);
for (int j = 0; j < S; ++j) {
X[j] = TreeSol::switches[j].x;
Y[j] = TreeSol::switches[j].y;
}
answer(C, X, Y);
}
