#include "doll.h" #include <bits/stdc++.h> using namespace std; 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; vector<vector<int>> edge(M + 1); for (int i = 0; i < N; i++) { edge[A[i]].push_back(A[i + 1]); } C[0] = A[0]; for (int m = 1; m <= M; m++) { if (edge[m].empty()) {} else if (edge[m].size() == 1) { C[m] = edge[m][0]; } else { int L = edge[m].size(); int b = 32 - __builtin_clz(L - 1); int K = (1 << b); C[m] = -X.size() - 1; int xsz = X.size(); for (int i = 0; i < K / 2 - 1; i++) { X.push_back(-xsz - (i + 1) * 2); Y.push_back(-xsz - (i + 1) * 2 - 1); } for (int i = K / 2 - 1; i < K - 1; i++) { X.push_back(C[m]); Y.push_back(C[m]); } 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()); } vector<int> u(K); for (int i = 0; i < K; i++) { u[v[i]] = i; } for (int i = 0; i < K / 2; i++) { X[xsz + K / 2 - 1 + u[i] / 2] = edge[m][i]; } for (int i = K / 2; i < K; i++) { if (i >= L - 1) { Y[xsz + K / 2 - 1 + u[i] / 2] = -xsz - 1; } else { Y[xsz + K / 2 - 1 + u[i] / 2] = edge[m][i]; } } Y.back() = edge[m][L - 1]; } } answer(C, X, Y); }