Submission #779461

#TimeUsernameProblemLanguageResultExecution timeMemory
779461amunduzbaevMechanical Doll (IOI18_doll)C++17
84 / 100
120 ms15144 KiB
#include "doll.h" #include "bits/stdc++.h" using namespace std; #ifndef EVAL #include "grader.cpp" #endif #define ar array typedef int64_t ll; typedef int32_t ii; //~ #define int ll void create_circuit(ii m, vector<ii> a){ a.push_back(0); int n = a.size(); int sz = 1; while(sz <= n) sz <<= 1; vector<int> used(sz * 2); function<void(int, int, int)> dfs = [&](int lx, int rx, int x){ if(rx + n <= sz){ return; } used[x] = 1; if(lx == rx){ return; } int m = (lx + rx) >> 1; dfs(lx, m, x << 1); dfs(m + 1, rx, x << 1 | 1); }; dfs(1, sz, 1); vector<int> sw(sz * 2), pos(sz); for(int i=0;i<sz;i++){ function<void(int, int, int)> go = [&](int x, int lx, int rx){ if(lx == rx){ pos[lx] = i; return; } int m = (lx + rx) >> 1; if(sw[x]) go(x << 1 | 1, m + 1, rx); else go(x << 1, lx, m); sw[x] ^= 1; }; go(1, 0, sz - 1); } int last = 0; vector<int> id; for(int i=0;i<sz;i++){ if(used[i]){ used[i] = -(++last); id.push_back(i); } else { used[i] = -1; } } vector<int> p(n); iota(p.begin(), p.end(), sz - n); sort(p.begin(), p.end(), [&](int i, int j){ return pos[i] < pos[j]; }); //~ for(int i=0;i<n;i++) cout<<a[i]<<" "; //~ cout<<"\n"; for(int i=0;i<n;i++){ used[sz + p[i]] = a[i]; } for(int i=0;i<sz - n;i++){ used[sz + i] = -1; } vector<int> c(m + 1, -1), x(last), y(last); for(int i=0;i<last;i++){ x[i] = used[id[i] << 1]; y[i] = used[id[i] << 1 | 1]; } answer(c, x, y); //~ for(int i=0;i<=m;i++) cout<<c[i]<<" "; //~ cout<<"\n"; //~ for(int i=0;i<last;i++){ //~ cout<<x[i]<<" "<<y[i]<<"\n"; //~ } }
#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...