Submission #1240718

#TimeUsernameProblemLanguageResultExecution timeMemory
1240718nikdMechanical Doll (IOI18_doll)C++20
43 / 100
59 ms13232 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; void create_circuit(int M, std::vector<int> A) { vector<vector<int>> next(M+1); next[0].push_back(A[0]); int n = A.size(); for(int i = 0; i<n-1; i++){ next[A[i]].push_back(A[i+1]); } next[A[n-1]].push_back(0); int s = 0; vector<int> c(M+1); vector<int> x, y; for(int i = 0; i<=M; i++){ if(next[i].empty()) c[i] = 0; else if(next[i].size() == 1) c[i] = next[i][0]; else{ c[i] = -(++s); int ns = 1; while(ns < next[i].size()) ns <<= 1; for(int jj = 0; jj<ns; jj++){ x.push_back(0); y.push_back(0); } int idx = 0; auto build = [&](auto&& build, int curr, int pow2, int md)->void{ int md1 = md; int md2 = md+pow2; pow2 <<= 1; if(next[i].size()<= pow2){ int dlt = pow2-next[i].size(); x[curr-1] = ((md1 < dlt ? c[i] : next[i][md1-dlt])); y[curr-1] = ((md2 < dlt ? c[i] : next[i][md2-dlt])); } else{ x[curr-1] = (-(++s)); y[curr-1] = (-(++s)); build(build, -x[curr-1], pow2, md1); build(build, -y[curr-1], pow2, md2); } }; build(build, -c[i], 1, 0); } } answer(c, x, y); //answer(C, X, Y); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...