#include "doll.h" #include <bits/stdc++.h> using namespace std; #define INF 1000000000 void create_circuit(int M, vector<int> A) { int N = A.size(); A.push_back(0); vector<int> C(M + 1); vector<int> X, Y; C[0] = A[0]; if (N == 1) { C[A[0]] = 0; } else { for (int i = 1; i <= M; i++) { C[i] = -1; } int L = N; int b = 32 - __builtin_clz(L - 1); int K = (1 << b); vector<bool> rem(K + 1); vector<pair<int, int>> swt(K + 1); for (int i = 1, l = b - 1; l >= 0; l--, i = i + i + 1) { if ((K - L) & (1 << l)) { swt[i].first = -1; int ll = i + i, rr = ll + 1; for (int c = 0; c < l; c++, ll += ll, rr += rr) { for (int j = ll; j < rr; j++) { rem[j] = true; swt[j].first = swt[j].second = -1; } } } } int idx = 1; vector<int> nid(K + 1); for (int i = 1; i <= K; i++) { if (!rem[i]) { nid[i] = idx++; } } vector<int> v; for (int i = 0; i < K; i++) { bitset<32> bs(i); for (int j = 0; j < b / 2; j++) { bool t = bs[j]; bs[j] = bs[b - j - 1]; bs[b - j - 1] = t; } v.push_back(bs.to_ulong()); } for (int i = 0, k = K / 2; i < K; i += 2, k++) { if (swt[k].first == -1) { v[i] = INF; } if (swt[k].second == -1) { v[i + 1] = INF; } } vector<int> stv = v; sort(stv.begin(), stv.end()); for (int i = 0; i < K; i++) { if (v[i] != INF) { v[i] = lower_bound(stv.begin(), stv.end(), v[i]) - stv.begin(); } } vector<int> xid, yid; for (int i = 0, k = K / 2; k < K; i += 2, k++) { if (swt[k].first != -1) { xid.push_back(v[i]); } if (swt[k].second != -1) { yid.push_back(v[i + 1]); } } reverse(xid.begin(), xid.end()); reverse(yid.begin(), yid.end()); for (int i = 1; i < K / 2; i++) { if (!rem[i]) { if (swt[i].first != -1) { X.push_back(-nid[i + i]); } else { X.push_back(-1); } if (swt[i].second != -1) { Y.push_back(-nid[i + i + 1]); } else { Y.push_back(-1); } } } for (int i = K / 2; i < K; i++) { if (!rem[i]) { if (swt[i].first != -1) { X.push_back(A[xid.back() + 1]); xid.pop_back(); } else { X.push_back(-1); } if (swt[i].second != -1) { Y.push_back(A[yid.back() + 1]); yid.pop_back(); } else { Y.push_back(-1); } } } Y.back() = 0; } answer(C, X, Y); }