# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
259846 | medk | Mechanical Doll (IOI18_doll) | C++14 | 0 ms | 0 KiB |
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>
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()
using namespace std;
vector<int> seq,X,Y,C;
int sz,dpth,layer;
void dfs(int u, int d, int v){
if(d<dpth){
dfs(u*2,d+1,v);
dfs(u*2+1,d+1,v+(1<<(d-1)));
X[u-1]=-u*2; Y[u-1]=X[u-1]-1;
//cout<<u<<" "<<X[u-1]<<' '<<Y[u-1]<<endl;
}
else{
X[u-1]=(v>=sz-1?-1:seq[v]);
if(v+(1<<(d-1))==(1<<dpth)-1) Y[u-1]=0;
else Y[u-1]=(v+(1<<(d-1))>=sz-1?-1:seq[v+(1<<(d-1))]);
//cout<<u<<" "<<X[u-1]<<' '<<Y[u-1]<<endl;
}
}
void create_circuit(int M, vector<int> A){
seq=A;
sz=sz(seq)+1;
dpth=ceil(log2(sz));
layer=(1<<dpth)-1;
X.resize(layer), Y.resize(layer), C.resize(M+1);
dfs(1,1,0);
for(int i=0;i<=M;i++) C[i]=0;
answer(C,X,Y);
}
/*
int main(){
int m,n; cin>>m>>n;
vector<int> tmp(n);
for(int i=0;i<n;i++) cin>>tmp[i];
create_circuit(m,tmp);
}*/