Submission #611994

#TimeUsernameProblemLanguageResultExecution timeMemory
611994krit3379Mechanical Doll (IOI18_doll)C++17
53 / 100
203 ms32308 KiB
#include<bits/stdc++.h> #include "doll.h" using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define N 500005 int l[N],r[N],sz,now; bool sw[N]; vector<int> c,x,y,pos[N]; map<int,int> mp; int bi(int x){ int i=1; while(i<x)i<<=1; return i; } int bic(int x){ int i=1,cnt=0; while(i<x)i<<=1,cnt++; return cnt; } int cre(int lev){ int s=++sz; if(lev==1){ l[s]=-1; r[s]=-1; return s; } l[s]=(cre(lev-1)); r[s]=(cre(lev-1)); return s; } void dfs(int s,int st,int head,vector<int> &a){ if(now<=0)return ; if(!sw[s]){ sw[s]^=1; if(l[s]==-1){ int ps=pos[head].size(); if(now<=ps)l[s]=-a[pos[head][ps-now]+1]; else l[s]=st; now--; dfs(st,st,head,a); } else dfs(l[s],st,head,a); } else{ sw[s]^=1; if(r[s]==-1){ int ps=pos[head].size(); if(now<=ps)r[s]=-a[pos[head][ps-now]+1]; else r[s]=st; now--; dfs(st,st,head,a); } else dfs(r[s],st,head,a); } } void create_circuit(int m,vector<int> a){ int i; c.resize(m+1); c[0]=a[0]; i=0; for(auto x:a){ mp[x]++; pos[x].push_back(i); i++; } a.push_back(0); for(auto [x,y]:mp){ if(mp[x]==1)c[x]=a[pos[x][0]+1]; else{ now=bi(y); c[x]=-cre(bic(y)); dfs(-c[x],-c[x],x,a); } } for(i=1;i<=sz;i++)x.push_back(-l[i]),y.push_back(-r[i]); 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...