// 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;
};
const int TO_PROCESS_OFFSETTER = 1000000;
int construct_switches(int cur_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
// ! Oh btw, I added "TO_PROCESS_OFFSETTER" to indicate that the switch exit still needs to be processed, haha
// ! Otherwise, the algorithm might relabel some of the already processed exits and cause wrong motion, haha
if(num_to_remove == 1) {
switches_to_construct.pb({cur_switch_num, -1, TO_PROCESS_OFFSETTER + (p2 << 1) + offset - ((p2 << 1) - 1)});
} else {
switches_to_construct.pb({cur_switch_num, TO_PROCESS_OFFSETTER + p2 + offset - ((p2 << 1) - 1), TO_PROCESS_OFFSETTER + (p2 << 1) + offset - ((p2 << 1) - 1)});
}
return cur_switch_num - 1;
} else {
if(num_to_remove < (size >> 1)) {
// Recursive case
pot_switch sw = {cur_switch_num, cur_switch_num - 1, -1};
// Recurse left
int next_switch_num = construct_switches(cur_switch_num - 1, num_to_remove, p2 << 1, offset + p2, size >> 1, switches_to_construct);
sw.y = next_switch_num;
// Recurse right
next_switch_num = construct_switches(next_switch_num, 0, p2 << 1, offset + (p2 << 1), size >> 1, switches_to_construct);
switches_to_construct.pb(sw);
return next_switch_num;
} else {
// Recursive case
pot_switch sw = {cur_switch_num, -1, cur_switch_num - 1};
// Recurse right
int next_switch = construct_switches(cur_switch_num - 1, num_to_remove - (size >> 1), p2 << 1, offset + (p2 << 1), size >> 1, switches_to_construct);
switches_to_construct.pb(sw);
return next_switch;
}
}
}
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 (see https://music.youtube.com/watch?v=ZEy36W1xX8c)
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>> exits_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) {
exits_to_renumber.push({sw.x, i});
}
if(sw.y >= 0) {
exits_to_renumber.push({sw.y, i});
}
}
int ptr = 0;
while(!exits_to_renumber.empty()) {
pi top_elem = exits_to_renumber.top();
int num = top_elem.first, i = top_elem.second;
exits_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++;
}
sort(switches_to_construct.begin(), switches_to_construct.end(), [](pot_switch s1, pot_switch s2){return s1.id > s2.id;});
LI(i, 0, (int)switches_to_construct.size()) {
// cout << switches_to_construct[i].id << " " << switches_to_construct[i].x << " " << switches_to_construct[i].y << endl;
x.pb(switches_to_construct[i].x);
y.pb(switches_to_construct[i].y);
}
answer(c, x, y);
return;
}
