This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |