Submission #312707

#	Time	Username	Problem	Language	Result	Execution time	Memory
312707		amunduzbaev	Mechanical Doll (IOI18_doll)	C++14	0 / 100	2 ms	352 KiB

doll

//#include "grader.cpp"
#include "doll.h"
#include <bits/stdc++.h>
#define pb(n) push_back(n)
using namespace std;
const int N=1e5+5;
void create_circuit(int m, vector<int> a) {
    int n,ind=0,ans,i;
    vector<vector<int>>way(m+1);
    vector<int>x,y,c(m+1);
    a.pb(0);
    n=a.size();
    for(i=0;i<n;i++){
        way[a[i]].pb(a[(i+1)%n]);
    }
    int s=a.size();
    if(!s) ans=0;
    else if(s==1) ans=a[0];
    else{
        int j,k=1,K=0;
        while(k<s){
            k*=2;
            K++;
        }

        vector<int>rev(k);
        for(j=0;j<k;j++)
            rev[j]=rev[j/2]/2|((j&1)<<(K-1));

        int id=--ind;
        for(int l=0;l<K-1;l++){
            for(j=0;j<(1<<l);j++){
                if((j<<(K-l))+(1<<(K-l)) <= k-s){}
                else if((j<<(K-l))+(1<<(K-l-1)) <= k-s){
                    x.pb(id);
                    y.pb(--ind);
                }else{
                    x.pb(--ind);
                    y.pb(--ind);
                }
            }
        }

        vector<int>go(k);
        int p=0;
        for(j=0;j<k;j++){
            if(rev[j]<k-s){}
            else go[rev[j]]=a[p++];
        }
        for(j=0;j<k/2;j++){
            if((j*2)+2 <= k-s){}
            else if((j<<1)+1 <= k-s){
                x.pb(id);
                y.pb(go[j*2+1]);
            }else{
                x.pb(go[j*2]);
                y.pb(go[j*2+1]);
            }
        }
        ans=id;
    }
    for(int i=0;i<=n;i++) c[i]=ans;
    /*
    for(int i=0;i<c.size();i++) cout<<c[i]<<" ";
    cout<<"\n";
    for(int i=0;i<x.size();i++) cout<<x[i]<<" ";
    cout<<'\n';
    for(int i=0;i<y.size();i++) cout<<y[i]<<" ";
    cout<<'\n';
    */
    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: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56