// AM+DG
/*
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
#define L(i, varmn, varmx) for(ll i = varmn; i < varmx; i++)
#define LR(i, varmx, varmn) for(ll i = varmx; i > varmn; i--)
#define LI(i, varmn, varmx) for(int i = varmn; i < varmx; i++)
#define LIR(i, varmx, varmn) for(int i = varmx; i > varmn; i--)
#define pb push_back
#include "doll.h"
struct pot_switch {
int id;
int x;
int y;
};
void construct_switches(int base_switch_num, int num_to_remove, int p2, int offset, int size, vector<pot_switch>& switches_to_construct) {
if(size == 2) {
// Handle the special case here
if(num_to_remove == 1) {
switches_to_construct.pb({base_switch_num - offset, -1, (p2 << 1) + offset - ((p2 << 1) - 1)});
} else {
switches_to_construct.pb({base_switch_num - offset, p2 + offset - ((p2 << 1) - 1), (p2 << 1) + offset - ((p2 << 1) - 1)});
}
} /* (No need for this, we're making a perfect binary tree anyways) else if(size == 3) {
// Handle the special case here
if(num_to_remove == 2) {
switches_to_construct.pb({base_switch_num - offset, -1, (p2 << 1) + offset - ((p2 << 1) - 1)});
} else {
switches_to_construct.pb({base_switch_num - offset, base_switch_num - (offset + p2), (p2 << 1) + offset - ((p2 << 1) - 1)});
// Recurse towards the first child
construct_switches(base_switch_num, num_to_remove, p2 << 1, offset + p2, size - (size >> 1), switches_to_construct);
}
}*/ else {
if(num_to_remove < (size >> 1)) {
// Recursive case
switches_to_construct.pb({base_switch_num - offset, base_switch_num - (offset + p2), base_switch_num - (offset + (p2 << 1))});
// Recurse left
construct_switches(base_switch_num, num_to_remove, p2 << 1, offset + p2, size >> 1, switches_to_construct);
// Recurse right
construct_switches(base_switch_num, 0, p2 << 1, offset + (p2 << 1), size >> 1, switches_to_construct);
} else {
// Recursive case
switches_to_construct.pb({base_switch_num - offset, -1, base_switch_num - (offset + (p2 << 1))});
// Recurse right
construct_switches(base_switch_num, num_to_remove - (size >> 1), p2 << 1, offset + (p2 << 1), size >> 1, switches_to_construct);
}
}
}
int ceillog2(int n) {
int p2 = 1;
while(p2 < n) {
p2 <<= 1;
}
return p2;
}
void create_circuit(int m, std::vector<int> a) {
a.pb(0); // Zero ni natte.. zero ni natte.. /ref
int n = a.size();
vi c(m + 1);
for (int i = 0; i <= m; ++i) {
c[i] = -1;
}
vi x;
vi y;
int actual_size = ceillog2(n);
int to_remove = actual_size - n;
vector<pot_switch> switches_to_construct;
construct_switches(-1, to_remove, 1, 0, actual_size, switches_to_construct);
priority_queue<pi, vector<pi>, greater<pi>> switches_to_renumber;
int num_switches = switches_to_construct.size();
LI(i, 0, num_switches) {
pot_switch sw = switches_to_construct[i];
if(sw.x >= 0) {
switches_to_renumber.push({sw.x, i});
}
if(sw.y >= 0) {
switches_to_renumber.push({sw.y, i});
}
}
int ptr = 0;
while(!switches_to_renumber.empty()) {
pi top_elem = switches_to_renumber.top();
int num = top_elem.first, i = top_elem.second;
switches_to_renumber.pop();
if(switches_to_construct[i].x == num) {
switches_to_construct[i].x = a[ptr];
} else {
switches_to_construct[i].y = a[ptr];
}
ptr++;
}
assert(ptr == n);
sort(switches_to_construct.begin(), switches_to_construct.end(), [](pot_switch s1, pot_switch s2){return s1.id > s2.id;});
LI(i, 0, n + 1) {
x.pb(switches_to_construct[i].x);
y.pb(switches_to_construct[i].y);
}
answer(c, x, y);
return;
}
