# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1214880 | thangdz2k7 | 자동 인형 (IOI18_doll) | C++20 | 0 ms | 0 KiB |
//#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void create_circuit(int M, vector <int> A){
vector <int> C(M + 1, -1);
vector <int> X, Y;
int nNode = 0;
A.push_back(0);
int N = A.size();
int b = 1;
while (b < N) b *= 2;
function <int(int, int)> dfs = [&](int l, int r){
if (l >= N) return -1;
if (l < r){
int mid = l + r >> 1;
nNode ++; int cur = nNode;
X.push_back(dfs(l, mid));
Y.push_back(dfs(mid + 1, r));
return -cur;
}
return 1;
};
dfs(0, b);
vector <int> vis(nNode, 0);
for (int i : A){
int u = 0;
while (u > -1){
vis[u] ^= 1;
int &to = vis[u] ? X[u] : Y[u];
if (to > 0) to = i, u = -1;
else u = -(to + 1);
}
}
answer(C, X, Y);
}