ioi 2018 mechanical doll (WIP)

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;



const int UNSET = -69696969;

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    int S = 1;
    while (S <= N+1) S *= 2;
    --S;

    vector<int> C(M+1);
    for (int i = 0; i <= M; ++i) {
        C[i] = -1;
    }

    vector<int> X(S, UNSET), Y(S, UNSET);
    vector<int> parent(S, UNSET);
    vector<int> numv(S, 0);
    int extra = S - N;

    cout << "N=" << N << "\nS=" << S << endl;
    cout << "extra=" << extra << "\n";
    parent[-(-1)-1] = 0;
    for (int n = -1; 2*(-n) <= S; --n) {
        X[-n-1] = 2*n;
        Y[-n-1] = 2*n-1;
        parent[2*(-n)-1] = n;
        parent[2*(-n)] = n;
    }
    for (int n = -(S/2 + 1); -n <= S; --n) {
        if (extra == 0) break;
        if (X[-n-1] == UNSET) {
            X[-n-1] = -1;
            --extra;
        }
        if (extra == 0) break;
        if (Y[-n-1] == UNSET) {
            Y[-n-1] = -1;
            --extra;
        }
    }
    Y[-(-S)-1] = 0;
    cout << endl;
    for (int i = 0; i < N; ++i) {
        int n = -1;
        cout << "i=" << i << " A[i]=" << A[i] << endl;
        ++numv[-n-1];
        while (X[-n-1] != UNSET && Y[-n-1] != UNSET) {
            if (numv[-n-1] % 2 == 1) {
                n = X[-n-1];
            } else {
                n = Y[-n-1];
            }
            ++numv[-n-1];
            cout << "n=" << n << endl;
        }
        cout << "\n";
        if (X[-n-1] == UNSET) {
            X[-n-1] = A[i];
        } else {
            Y[-n-1] = A[i];
        }
    }
    for (int n = -S; n <= -1; ++n) {
        cout << "n=" << n << "; pr=" << parent[-n-1] << " chld=" << X[-n-1] << "," << Y[-n-1] << endl;
        if (X[-n-1] == Y[-n-1]/* || X[-n-1] == -1 || Y[-n-1] == -1*/) {
            int trg = X[-n-1] == -1 ? Y[-n-1] : X[-n-1];
            cout << "redundant: trg=" << trg << "\n";
            if (n == X[-parent[-n-1]-1]) {
                X[-parent[-n-1]-1] = trg;
            } else {
                Y[-parent[-n-1]-1] = trg;
            }
        }
    }

    for (int n = -1; -n <= S; --n) {
        numv[-n-1] = 0;
    }

    int S1 = 0;
    vector<int> newid(S, UNSET);
    vector<int> oldid(S, UNSET);

    cout << "\nSIMULATION:\n";

    {
        int n = 0;
        do {
            cout << "n=" << n << endl;
            if (n >= 0) {
                n = C[n];
            } else {
                if (newid[-n-1] == UNSET) {
                    cout << "new, S1=" << S1 << endl;
                    ++S1;
                    newid[-n-1] = -S1;
                    oldid[S1-1] = n;
                }
                ++numv[-n-1];
                if (numv[-n-1] % 2 == 1) {
                    n = X[-n-1];
                } else {
                    n = Y[-n-1];
                }
            }
        } while (n != 0);
    }

    cout << "\nNEW:\n";
    cout << "S1=" << S1 << endl;

    for (int n = -1; n >= -S; --n) {
        cout << "n=" << n << " newid=" << newid[-n-1] << "  oldid=" << oldid[-n-1] << endl;
    }
    cout << endl;

    vector<int> X1(S1), Y1(S1);
    for (int n = -1; n >= -S1; --n) {
        X1[-n-1] = newid[-X[-oldid[-n-1]-1]-1];
        Y1[-n-1] = newid[-Y[-oldid[-n-1]-1]-1];
        cout << "n=" << n << " X=" << X1[-n-1] << " Y=" << Y1[-n-1] << endl;
    }

    answer(C, X1, Y1);
}