Submission #1132003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132003		StefanSebez	Mechanical Doll (IOI18_doll)	C++20	85.55 / 100	76 ms	24356 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50;
vector<int>C,X,Y;
vector<int>susedni[N];
int LOG[2*N+50];
int S;
void Resi(int &c,int ss,int se,int broj,int rt,vector<int>&a){
    if(broj-1>=se){c=rt;return;}
    c=-(++S);int ind=S;
    if(ss+1==se){
        int n=a.size();
        int k=ss>>1,L=LOG[n]-1;
        vector<int>bits;
        while(L--) bits.pb(k&1),k>>=1;
        k=0;for(int i=bits.size()-1,e=1;i>=0;i--,e<<=1) if(bits[i]) k+=e;
        X[ind]=a[k];
        Y[ind]=a[k+n/2];
        //printf("%i %i %i: %i %i\n",ss,se,c,X[ind],Y[ind]);
        return;
    }
    int mid=ss+se>>1;
    Resi(X[ind],ss,mid,broj,rt,a);
    Resi(Y[ind],mid+1,se,broj,rt,a);
    //printf("%i %i %i: %i %i\n",ss,se,c,X[ind],Y[ind]);
}
void create_circuit(int m,vector<int> A) {
    for(int i=1,e=1,ct=-1;i<=2*N;i++){if(i==e)e<<=1,ct++;LOG[i]=ct;}
    A.pb(0);int n=A.size();
    for(int i=0;i<m+1;i++) C.pb(0);
    C[0]=A[0];
    X.pb(0),Y.pb(0);
    X.resize(5*N),Y.resize(5*N);
    for(int i=0;i<n;i++) susedni[A[i]].pb(A[i+1]);
    for(int i=1;i<=m;i++){
        int k=susedni[i].size();
        if(k==1) C[i]=susedni[i][0];
        if(k<=1) continue;
        int ct=0;
        for(int j=0,e=1;j<=29;j++,e<<=1) if(e>=k){ct=e-k,k=e;break;}
        vector<int>temp(k,0);
        for(int j=0,ind=ct;j<k/2;j++){
            vector<int>bits;int L=LOG[k]-1,K=j;
            while(L--) bits.pb(K&1),K>>=1;
            K=0;for(int i=bits.size()-1,e=1;i>=0;i--,e<<=1) if(bits[i]) K+=e;
            if(ind)temp[K]=-S-1,ind--;
            if(ind)temp[K+k/2]=-S-1,ind--;
        }
        for(int j=0,ind=0;j<k;j++){
            if(temp[j]==0) temp[j]=susedni[i][ind++];
        }
        /*reverse(susedni[i].begin(),susedni[i].end());
        while(susedni[i].size()<k) susedni[i].pb(-S-1);
        reverse(susedni[i].begin(),susedni[i].end());*/
        //printf("%i: ",i);for(auto j:temp) printf("%i ",j);printf("\n");
        Resi(C[i],0,k-1,ct,-S-1,temp);
    }
    //for(auto &i:X) i=-i;
    //for(auto &i:Y) i=-i;
    while(X.size()>S+1) X.pop_back();
    while(Y.size()>S+1) Y.pop_back();
    reverse(X.begin(),X.end());X.pop_back();reverse(X.begin(),X.end());
    reverse(Y.begin(),Y.end());Y.pop_back();reverse(Y.begin(),Y.end());
    answer(C, X, Y);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 41.553 / 56