Submission #713742

#TimeUsernameProblemLanguageResultExecution timeMemory
713742LittleOrangeMechanical Doll (IOI18_doll)C++17
6 / 100
85 ms11660 KiB
#include "doll.h" #include<bits/stdc++.h> using namespace std; using ll = int; void create_circuit(int M, std::vector<int> A) { int N = A.size(); std::vector<int> C(M + 1,0); C[0] = A[0]; if (N == 1){ for (int i = 1; i <= M; ++i) C[i] = 0; vector<int> X,Y; answer(C, X, Y); return; } A.push_back(0); vector<vector<ll>> nxt(M); for(ll i = 0;i<N;i++){ nxt[A[i]-1].push_back(A[i+1]); } for(auto &o : nxt){ if (o.size()>2) o.resize(1<<(__lg(o.size()-1)+1),-1); } vector<int> X,Y; ll it = 0; vector<ll> CUR; ll root; function<ll(ll,ll,ll)> dfs; dfs = [&](ll cnt, ll st, ll lv){ //cerr << "dfs " << cnt << " " << st << " " << lv << "\n"; if (cnt==1){ return CUR[st]==-1?root:CUR[st]; } ll i = it++; X.push_back(dfs(cnt-cnt/2,st,lv+1)); Y.push_back(dfs(cnt/2,st+(1<<lv),lv+1)); return -1-i; }; for(ll i = 0;i<M;i++){ CUR = nxt[i]; if (CUR.size()>1){ C[i+1] = root = -1-it; dfs(CUR.size(),0,0); }else if(CUR.size()==1){ C[i+1] = CUR[0]; } } for(ll i = 0;i<N;i++) { //cerr << "nxt " << i << ":"; //for(ll j : nxt[i]) cerr << " " << j; //cerr << "\n"; } 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...