#include "doll.h"
#include <set>
#include <tuple>
#include <cassert>
#include <iostream>
using namespace std;
const int INF = 1e9;
// pair<int, int> findZero(int i, const vector<int> &X, const vector<int> &Y) {
// if (!X[-i]) return {i, 1};
// if (!Y[-i]) return {i, 2};
// if (X[-i] < 0) {
// pair<int, int> v = findZero(X[-i], X, Y);
// if (v.first) return v;
// }
// if (Y[-i] < 0) {
// pair<int, int> v = findZero(Y[-i], X, Y);
// if (v.first) return v;
// }
// return {0, 0};
// }
bool drain(int i, int root, vector<int> &X, vector<int> &Y) {
cerr << " draining from " << i << " root " << root << " with " << X[-i] << ' ' << Y[-i] << endl;
bool isDrain = false;
if (X[-i] < 0) {if (drain(X[-i], root, X, Y)) isDrain = true;}
else if (X[-i] == 0 || X[-i] == INF) X[-i] = root, isDrain = true, cerr << " changed X[" << i << "] = " << X[-i] << endl;
if (Y[-i] < 0) {if (drain(Y[-i], root, X, Y)) isDrain = true;}
else if (Y[-i] == 0 || Y[-i] == INF) Y[-i] = root, isDrain = true, cerr << " changed Y[" << i << "] = " << Y[-i] << endl;
return isDrain;
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
vector<vector<int>> nxt(1+M);
nxt[0].push_back(A[0]);
for (int i = 0; i < N-1; ++i) {
nxt[A[i]].push_back(A[i+1]);
}
nxt[A[N-1]].push_back(0);
int S = 0;
vector<int> X(1), Y(1);
vector<int> C(1+M); // root switch for each trigger
for (int i = 0; i <= M; ++i) {
if (nxt[i].empty()) { // unused trigger
C[i] = i;
continue;
}
int p2 = 1, expo = 0;
while (p2 < (int)nxt[i].size()) ++expo, p2 <<= 1;
// Order targets (stored in nxt) for tree of switches
vector<int> orderedNxt(1, 0);
for (int j = 1, previousPow2 = 1; j <= expo; ++j, previousPow2 <<= 1) {
vector<int> nextLevel(2*orderedNxt.size());
for (int k = 0; k < (int)nextLevel.size(); ++k) {
nextLevel[k] = orderedNxt[k>>1] + (k&1)*previousPow2;
}
orderedNxt = nextLevel;
}
for (int j = 0; j < p2; ++j) {
if (orderedNxt[j] >= (int)nxt[i].size()) orderedNxt[j] = INF;
else orderedNxt[j] = nxt[i][orderedNxt[j]];
}
set<pair<pair<int, int>, int>> gotSwitches;
// Now build switches for pairs of targets
vector<int> curSwitches = orderedNxt;
while (curSwitches.size() > 1) {
vector<int> nextSwitches((int)curSwitches.size()>>1);
for (int j = 0; j < (int)nextSwitches.size(); ++j) {
int x = curSwitches[2*j], y = curSwitches[2*j+1];
if (x==INF && y==INF) {// this should never happen
nextSwitches[j] = INF;
continue;
}
// create switch
auto it = gotSwitches.lower_bound({{x, y}, 0});
if (x != INF && y != INF && it != gotSwitches.end() && it->first.first == x && it->first.second == y) {
nextSwitches[j] = -it->second; // Use existing switch
} else { // Create new switch since it does not already exist
++S;
X.push_back(x);
Y.push_back(y);
gotSwitches.insert({{x, y}, S});
nextSwitches[j] = -S;
}
}
curSwitches = nextSwitches;
}
// now curSwitches[0] is the root switch for this trigger
C[i] = curSwitches[0];
}
cerr << " THERE ARE " << S << " switches\n";
for (int i = 1; i <= S; ++i) cerr << i << ' ' << X[i] << ' ' << Y[i] << endl;
cerr << " ROOTS ARE ";
for (int i = 0; i <= M; ++i) cerr << i << ' ' << C[i] << endl;
// Now we need to "drain" the switches at the end so they all have state X at the end
// find the roots of the trees that need draining
cerr << "WHO NEEDS DRAINING?" << endl;
vector<int> needDrain;
for (int i = 0; i <= M; ++i) {
if (C[i] >= 0) {
if (C[i] == 0 || C[i] == INF) C[i] = i;
} else if (drain(C[i], C[i], X, Y) && i != A[N-1]) {
needDrain.push_back(i);
cerr << ' ' << i << endl;
}
}
auto getBottom = [&C, &Y](int i) {
int root = C[i]; i = C[i];
while (true) {
if (i > 0) {
if (C[i] == root) return i;
i = C[i];
} else {
if (Y[-i] == root) return i;
i = Y[-i];
}
}
};
// link up the drain chain drain chain
int prevBottom = getBottom(A[N-1]);
for (int i : needDrain) {
cerr << " CONNECTING PREVIOUS BOTTOM " << prevBottom << " TO C[" << i << "] = " << C[i] << endl;
// connect bottom (end) of previous to root of current
if (prevBottom > 0) C[prevBottom] = C[i];
else Y[-prevBottom] = C[i];
// find bottom of current
prevBottom = getBottom(i);
}
cerr << " ROOT NOW ON " << C[A[N-1]] << endl;
// connect last bottom back to the origin
if (prevBottom > 0) C[prevBottom] = 0;
else Y[-prevBottom] = 0;
cerr << " now connected " << prevBottom << " to " << 0 << endl;
cerr << " THERE ARE " << S << " switches\n";
for (int i = 1; i <= S; ++i) cerr << i << ' ' << X[i] << ' ' << Y[i] << endl;
cerr << " ROOTS ARE ";
for (int i = 0; i <= M; ++i) cerr << i << ' ' << C[i] << endl;
X.erase(X.begin());
Y.erase(Y.begin());
answer(C, X, Y);
}
