Submission #760835

#TimeUsernameProblemLanguageResultExecution timeMemory
760835alexander707070Mechanical Doll (IOI18_doll)C++14
70.67 / 100
237 ms11356 KiB
#include<bits/stdc++.h> #include "doll.h" #define MAXN 800007 using namespace std; int m,power,n,num; int a[MAXN],s,ind[MAXN],temp[MAXN]; int lt[MAXN],rt[MAXN]; vector<int> from,to,c; int rev(int x){ int res=0; for(int i=1;i<power;i*=2){ res*=2; res+=x%2; x/=2; } return res; } void build(int v,int l,int r){ if(l+1==r){ if(l<n)lt[v]=a[l]; else lt[v]=-1; if(r<n)rt[v]=a[r]; else if(r==power-1)rt[v]=0; else rt[v]=-1; }else{ int tt=(l+r)/2; if(l>=n and tt<power-1){ lt[v]=-1; }else{ num++; lt[v]=-num; build(num,l,tt); } if(tt+1>=n and r<power-1){ rt[v]=-1; }else{ num++; rt[v]=-num; build(num,tt+1,r); } } } bool cmp(int x,int y){ return rev(x)<rev(y); } void create_circuit(int M, vector<int> A){ m=M; n=int(A.size()); for(int i=0;i<n;i++){ a[i]=A[i]; ind[i]=i; } power=1; num=1; while(power<n+1)power*=2; sort(ind,ind+n,cmp); for(int i=0;i<n;i++)temp[ind[i]]=a[i]; for(int i=0;i<n;i++)a[i]=temp[i]; build(1,0,power-1); for(int i=0;i<=m;i++)c.push_back(-1); for(int i=1;i<=num;i++){ from.push_back(lt[i]); to.push_back(rt[i]); } answer(c,from,to); } /* int main(){ create_circuit(4, {1, 2, 1,3,2,4,3,1,2}); } */
#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...