#include "doll.h"
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#include <cstdio>
using namespace std;
namespace TreeSol {
typedef vector<int> VI;
const int UNDEFINED = 999999;
struct Node {
int L, R;
int id;
bool flipped, leaf;
Node(int _L = -1, int _R = -1, int _id = UNDEFINED)
: L(_L), R(_R), id(_id), flipped(false), leaf(false) {}
};
vector<Node> nodes;
void build_tree(int idx, int L, int R) {
if (L == R) {
nodes[idx] = Node(L, R);
nodes[idx].leaf = true;
return;
}
int mid = (L+R)/2;
nodes[idx] = Node(L, R, -idx);
build_tree(idx*2, L, mid);
build_tree(idx*2+1, mid+1, R);
}
void assign_device_id(int id, int from, int idx = 1) {
if (nodes[idx].L == nodes[idx].R) {
if (nodes[idx].L >= from)
nodes[idx].id = id;
else {
nodes[idx].id = -1;
assign_device_id(id, from);
}
return;
}
nodes[idx].flipped = !nodes[idx].flipped;
if (nodes[idx].flipped)
assign_device_id(id, from, 2*idx);
else
assign_device_id(id, from, 2*idx+1);
}
void compress_tree(int idx = 1) {
if (nodes[idx].L == nodes[idx].R)
return;
compress_tree(idx*2);
compress_tree(idx*2 + 1);
if (nodes[idx*2].leaf && nodes[idx*2+1].leaf &&
nodes[idx*2].id == nodes[idx*2+1].id) {
nodes[idx].leaf = true;
nodes[idx].id = nodes[idx*2].id;
}
}
void reassign_switch_ids(map<int,int>& reassigned_ids,
int& last_switch_id, int idx = 1) {
int id = nodes[idx].id;
if (id < 0) {
if (reassigned_ids.count(id))
nodes[idx].id = reassigned_ids[id];
else {
last_switch_id++;
nodes[idx].id = reassigned_ids[id] = -last_switch_id;
}
}
if (nodes[idx].leaf)
return;
if (nodes[idx].L == nodes[idx].R)
return;
reassign_switch_ids(reassigned_ids, last_switch_id, idx*2);
reassign_switch_ids(reassigned_ids, last_switch_id, idx*2 + 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].leaf) return;
int id = nodes[idx].id;
if (id < 0) {
id = -(id+1);
switches[ id ].x = nodes[idx*2 ].id;
switches[ id ].y = nodes[idx*2+1].id;
}
assign_switch_exits(idx*2);
assign_switch_exits(idx*2 + 1);
}
int build_circuit(int src, const VI& nxt) {
int K = nxt.size();
if (K == 1)
return nxt[0];
if (count(nxt.begin(), nxt.end(), nxt[0]) == K)
return nxt[0];
int nodes_last_level = 1;
while (nodes_last_level < K)
nodes_last_level *= 2;
nodes = vector<Node>(2*nodes_last_level);
build_tree(1, 0, nodes_last_level-1);
int from = nodes_last_level - K;
for (int dev_id : nxt)
assign_device_id(dev_id, from);
/*
fprintf(stderr, "src: %d\n", src);
fprintf(stderr, "nodes_last_level:%d K:%d\n", nodes_last_level, K);
*/
/*
fprintf(stderr, "After assigned device ids\n");
for (int idx = 1; idx < int(nodes.size()); ++idx) {
Node x = nodes[idx];
fprintf(stderr, "%3d [%d,%d] id:%d leaf:%d\n", idx, x.L, x.R, x.id, x.leaf);
}
fprintf(stderr, "\n");
*/
compress_tree();
/*
fprintf(stderr, "After compression\n");
for (int idx = 1; idx < int(nodes.size()); ++idx) {
Node x = nodes[idx];
fprintf(stderr, "%3d [%d,%d] id:%d leaf:%d\n", idx, x.L, x.R, x.id, x.leaf);
}
fprintf(stderr, "\n");
*/
int last_switch_id = switches.size();
map<int,int> reassigned_ids;
reassign_switch_ids(reassigned_ids, last_switch_id);
/*
fprintf(stderr, "After reassignment\n");
for (int idx = 1; idx < int(nodes.size()); ++idx) {
Node x = nodes[idx];
fprintf(stderr, "%3d [%d,%d] id:%d leaf:%d\n", idx, x.L, x.R, x.id, x.leaf);
}
fprintf(stderr, "\n");
*/
// fprintf(stderr, "last_switch_id:%d\n", last_switch_id);
switches.resize( last_switch_id );
assign_switch_exits();
// fprintf(stderr, "END\n\n");
return nodes[1].id;
}
}
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;
// fprintf(stderr, "j:%d x:%d y:%d\n", j, X[j], Y[j]);
}
answer(C, X, Y);
}
