#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> cnt(100001); for (int k = 0; k < N; k++) { cnt[A[k]]++; } vector<int> C(M + 1), swt(M + 1, -1); vector<int> X, Y; C[0] = A[0]; for (int i = 1; i <= N; i++) { int src = A[i - 1], des = A[i]; if (cnt[src] == 1) { C[src] = des; } else if (swt[src] == -1) { swt[src] = X.size(); X.push_back(INF), Y.push_back(INF); C[src] = -swt[src] - 1; X[swt[src]] = des; } else { Y[swt[src]] = des; } } answer(C, X, Y); }