#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 = { 1, -1}; vector<int> X, Y; int b = 32 - __builtin_clz(N - 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 - N) & (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++; } } for (int i = 1; i < K / 2; i++) { if (!rem[i]) { if (swt[i].first != -1) { X.push_back(-nid[i + i]); swt[i].first = nid[i + i]; } else { X.push_back(-1); } if (swt[i].second != -1) { Y.push_back(-nid[i + i + 1]); swt[i].second = 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(1); swt[i].first = 1; } else { X.push_back(-1); } if (swt[i].second != -1) { Y.push_back(1); swt[i].second = 1; } else { Y.push_back(-1); } } } Y.back() = 0; answer(C, X, Y); }