// 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, const vi& to_connect, int p2, int offset, int size, vector<pot_switch>& switches_to_construct) {
if(size == 2) {
// Handle the special case here
switches_to_construct.pb({base_switch_num - offset, to_connect[p2 + offset - ((p2 << 1) - 1)], to_connect[(p2 << 1) + offset - ((p2 << 1) - 1)]});
} else if(size == 3) {
// Handle the special case here
switches_to_construct.pb({base_switch_num - offset, base_switch_num - (offset + p2), to_connect[(p2 << 1) + offset - ((p2 << 1) - 1)]});
// Recurse towards the first child
construct_switches(base_switch_num, to_connect, p2 << 1, offset + p2, size - (size >> 1), switches_to_construct);
} else {
// 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, to_connect, p2 << 1, offset + p2, size - (size >> 1), switches_to_construct);
// Recurse right
construct_switches(base_switch_num, to_connect, 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) {
int n = a.size();
vi c(m + 1);
c[0] = -1;
for (int i = 1; i <= m; ++i) {
c[i] = 1;
}
// vi x(N), y(N);
// for (int k = 0; k < N; ++k) {
// x[k] = y[k] = a[k];
// }
vi x;
vi y;
vvi adjmat;
LI(i, 0, m + 1) {
vi adjmatr;
adjmat.pb(adjmatr);
}
LI(i, -1, n) {
if(i == -1) {
adjmat[0].pb(a[i + 1]);
} else if(i == n - 1) {
adjmat[a[i]].pb(0);
} else {
adjmat[a[i]].pb(a[i + 1]);
}
}
int last_switch = 0;
LI(i, 0, m + 1) {
int cur_num_next = adjmat[i].size();
if(cur_num_next == 0) {
c[i] = 0;
} else if(cur_num_next == 1) {
c[i] = adjmat[i][0];
} else {
/*
Construct switches needs...
whatever the last switch was,
the list of things it should connect the leaf node to
the current power of two separation (starts at 1 and doubles)
the current offset (starts at 0)
for the left tree, it increments by power * 1
for the right, its power * 2
Left tree must be of size ceil(N / 2)
right is size floor(N / 2)
*/
c[i] = last_switch - 1;
int actual_num_next = ceillog2(adjmat[i].size());
vi actual_next;
actual_next.reserve(actual_num_next);
LI(j, 0, actual_num_next - cur_num_next) {
actual_next.pb(last_switch - 1);
}
LI(j, 0, cur_num_next) {
actual_next.pb(adjmat[i][j]);
}
vector<pot_switch> switches_to_construct;
construct_switches(last_switch - 1, actual_next, 1, 0, actual_num_next, switches_to_construct);
sort(switches_to_construct.begin(), switches_to_construct.end(), [](pot_switch s1, pot_switch s2) {return s1.id > s2.id;}); // Sort by decreasing ID
LI(j, 0, actual_num_next - 1) {
x.pb(switches_to_construct[j].x);
y.pb(switches_to_construct[j].y);
}
last_switch -= actual_num_next - 1;
}
}
answer(c, x, y);
return;
}
