Submission #312714

#	Time	Username	Problem	Language	Result	Execution time	Memory
312714		amunduzbaev	Mechanical Doll (IOI18_doll)	C++14	100 / 100	149 ms	13420 KiB

doll

//#include "grader.cpp"
#include "doll.h"
#include <bits/stdc++.h>
#define pb(n) push_back(n)
using namespace std;
void create_circuit(int m, vector<int> a) {
    int n,ind=0,ans,i,s;
    vector<vector<int>>way(m+1);
    vector<int>x,y,c(m+1);
    a.pb(0);
    n=a.size(),s=n;
    for(i=0;i<n-1;i++){
        way[a[i]].pb(a[i+1]);
    }
    way[0].pb(a[0]);
    if(!s) ans=0;
    else if(s==1) ans=a[0];
    else{
        int j,k=1,K=0;
        while(k<s){
            k<<=1;
            K++;
        }
        vector<int>rev(k);
        for(j=0;j<k;j++)rev[j]=rev[j/2]/2|((j&1)<<(K-1));
        int iid=--ind;
        for(int lvl=0;lvl<K-1;lvl++){
            for(j=0;j<(1<<lvl);j++){
                if((j<<(K-lvl))+(1<<(K-lvl))<=(k-s)){}
                else if((j<<(K-lvl))+(1<<(K-lvl-1))<=(k-s)){
                    x.pb(iid);
                    y.pb(--ind);
                }
                else{
                    x.pb(--ind);
                    y.pb(--ind);
                }
            }
        }
        vector<int>go(k);
        int ptr=0;
        for(j=0;j<k;j++)
            if(rev[j]<(k-s)){}
            else go[rev[j]]=a[ptr++];
        for(j=0;j<k/2;j++){
            if((j<<1)+2<=(k-s)){}
            else if((j<<1)+1<=(k-s)){
                x.pb(iid);
                y.pb(go[(j<<1)+1]);
            }else{
                x.pb(go[j<<1]);
                y.pb(go[(j<<1)+1]);
            }
        }
        ans=iid;
    }
    for(i=0;i<=m;i++) c[i]=ans;
    answer(c,x,y);
}
/*
9 9
2 9 8 1 3 7 6 4 5

4 4
1 2 1 3

6 8
1 2 1 3 1 4 1 5
*/

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