Submission #312678

#	Time	Username	Problem	Language	Result	Execution time	Memory
312678		juggernaut	Mechanical Doll (IOI18_doll)	C++14	100 / 100	163 ms	13100 KiB

doll

#include"doll.h"
#include<bits/stdc++.h>
using namespace std;
void create_circuit(int M,vector<int>A){
    vector<vector<int>>after(M+1);
    vector<int>connected(M+1),x,y;
    A.push_back(0);
    int n=A.size(),i=0,s=0,id;
    for(;i<n;i++)
        after[A[i]].push_back(A[(i+1)%n]);
    int saizu=A.size();
    if(!saizu)id=0;
    else if(saizu==1)id=A[0];
    else{
        int j,k=1,K=0;
        while(k<saizu){
            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=--s;
        for(int lvl=0;lvl<K-1;lvl++){
            for(j=0;j<(1<<lvl);j++){
                if((j<<(K-lvl))+(1<<(K-lvl))<=(k-saizu)){}
                else if((j<<(K-lvl))+(1<<(K-lvl-1))<=(k-saizu)){
                    x.push_back(iid);
                    y.push_back(--s);
                }
                else{
                    x.push_back(--s);
                    y.push_back(--s);
                }
            }
        }
        vector<int>go(k);
        int ptr=0;
        for(j=0;j<k;j++)
            if(rev[j]<(k-saizu)){}
            else go[rev[j]]=A[ptr++];
        for(j=0;j<k/2;j++){
            if((j<<1)+2<=(k-saizu)){}
            else if((j<<1)+1<=(k-saizu)){
                x.push_back(iid);
                y.push_back(go[(j<<1)+1]);
            }else{
                x.push_back(go[j<<1]);
                y.push_back(go[(j<<1)+1]);
            }
        }
        id=iid;
    }
    for(i=0;i<=M;i++)connected[i]=id;
    answer(connected,x,y);
}

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