# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
789939 | 2023-07-22T07:54:41 Z | Trisanu_Das | Mechanical Doll (IOI18_doll) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "doll.h" using namespace std; vector<int> s; int x[300005], y[300005], vis[300005], v, b = 1, n; int dfs(int l, int r){ if(l >= n) return -1; if(r - l > 1){ int mid = (l + r) / 2, u = v++; y[u] = dfs(l, mid); x[u] = dfs(mid, r); return -(u + 1); } return 1; } void create_circuit(int m, vector<int> a){ s.assign(m + 1, -1); a.push_back(0); n = a.size(); while(b < n) b *= 2; dfs(0, b); for(int i : a){ int u = 0; while(u > -1){ vis[u] ^= 1; int &w = vis[u] ? x[u] : y[u]; if(w >= 0) w = i, u = -1; else u = -(w + 1); } } x.resize(v); y.resize(v); answer(s, x, y); }