#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void sub_form_array(int log2, vector<int> &arr, unordered_map<int, int> &idx)
{
arr[0] = 1;
for( int i = 1; i < (1<<log2) ; ++i )
{
// cerr << i*2 << " :IDX ARR: " << arr[i*2] << '\n';
if ( i%2 )
arr[i*2] = arr[i*2 - 2] + (1<<log2);
else
{
int divisible_by = (1<<log2);
while ( i % divisible_by )
divisible_by/=2;
if ( i*2 >= divisible_by*2 && arr[ i*2 - divisible_by ] > arr[ i*2 - divisible_by*2 ] )
{
arr[i*2] = arr[ i*2 - divisible_by ] - (1<<log2) / divisible_by;
}
else
arr[i*2] = arr[ i*2 - divisible_by ] + (1<<log2) / divisible_by*2;
}
idx[arr[i*2]] = i*2;
// cerr << i*2 << " :IDX ARR: " << arr[i*2] << '\n';
}
// for ( const int &a : arr )
// cerr << a << ' ';
// cerr << '\n';
for ( int i = (1<<log2+1); i < arr.size(); i += 2 )
{
arr[i] = arr[i - (1<<log2+1)] + 1;
idx[arr[i]] = i;
}
// for ( const int &a : arr )
// cerr << a << ' ';
}
vector<int> form_array( vector<int> d_adj )
{
unordered_map< int, int > idx;
int log2 = static_cast<int> ( log( (double)(d_adj.size()-1) ) / log ( 2 ) ) - 1; // static_cast seems better than implicit cast
int _2log = ( 1 << (log2 + 1) );
vector<int> arr( ( _2log*2 ) );
sub_form_array(log2, arr, idx);
int offset = d_adj.size() - _2log + 1;
for ( int n = _2log; n >= 1; --n )
{
int i = idx[n]+1;
int *a = &arr[ i ];
if ( 0 < (--offset) )
*a = ( _2log + offset );
else
{
*a = -1;
}
}
return arr;
}
int s_count = 0;
vector < int > C, X, Y;
unordered_map < int, int > parent;
int get_global_parent(int idx )
{
//assert(parent[idx] != 0);
if ( parent[idx] > 0 )
{
return idx;
}
return get_global_parent( parent[idx] );
}
void recursive_magic(int idx, int count, int arr_idx, vector<int> &arr, vector<int> &d_adj)
{
if ( idx > 0 )
{
++s_count;
parent[-s_count] = idx;
C[idx] = -s_count;
recursive_magic(-(s_count), count, arr_idx, arr, d_adj);
return;
}
X.push_back(0), Y.push_back(0);
if ( count == 2 ) // count will always reach 2 as count is always a power of 2
{
int a1 = arr[arr_idx];
int a2 = arr[arr_idx+1];
X[-idx - 1] = (a1 > 0? d_adj[a1-1] : get_global_parent(idx ));
Y[-idx - 1] = (a2 > 0? d_adj[a2-1] : get_global_parent(idx ));
return;
}
//assert(count >= 2);
int tmp = count/2;
int mid = arr_idx + tmp;
++s_count;
parent[-s_count] = idx;
X[-idx - 1] = -s_count;
recursive_magic(-(s_count), tmp, arr_idx, arr, d_adj);
++s_count;
parent[-s_count] = idx;
Y[-idx - 1] = -s_count;
recursive_magic(-(s_count), tmp, mid, arr, d_adj);
}
void create_circuit(int M, vector<int> A)
{
vector< vector<int> > directed_adj(M+1);
C.resize(M+1);
C[0] = A[0];
A.push_back(0);
for ( int _ = 0; _ < A.size()-1; ++_ )
{
directed_adj[ A[_] ].push_back( A[_+1] ); // I'll convert everything to a directed graph and make switches based on that
}
for ( int i = 1; i <= M; ++i )
{
if ( directed_adj[i].empty() )
continue;
else if ( directed_adj[i].size() == 1)
{
C[i] = directed_adj[i][0];
continue;
}
vector<int> arr = form_array( directed_adj[i] );
recursive_magic(i, arr.size(), 0, arr, directed_adj[i]);
}
// cerr << C.size() << '\n';
// for ( int i = 0; i < C.size(); ++i )
// cerr << C[i] << " :C | A: " << A[i] << '\n';
// cerr << X.size() << '\n';
// for ( int i = 0; i < X.size(); ++i )
// cerr << X[i] << " :X | Y: " << Y[i] << '\n';
answer(C, X, Y);
return;
}
