Submission #525093

#	Time	Username	Problem	Language	Result	Execution time	Memory
525093		leaked	Mechanical Doll (IOI18_doll)	C++14	53 / 100	149 ms	16656 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"


#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

void create_circuit(int m,vec<int> a){
    vec<int>c(m+1);
    vec<int> cnt(m+1,0);
    vec<vec<int>> goes(m+1,vec<int>());
    int n=0;
    for(int i=0;i<sz(a);i++){
        int nxt=(i+1==sz(a)?0:a[i+1]);
        goes[a[i]].pb(nxt);
    }
    vec<int>x,y;
    vec<int>curt;
    for(int i=1;i<=m;i++){
        if(sz(goes[i])==1){
            c[i]=goes[i].back();
            continue;
        }
        if(!sz(goes[i])) continue;
        vec<int>cur(sz(goes[i]),0);
        int lvl=ceil((double)log2(sz(goes[i])));
        int lt=lvl;
        while(sz(cur)!=pw(lvl)) cur.pb(0);
        while(lvl!=0){
            vec<int>nc;
            for(int j=0;j<sz(cur);j+=2){
                nc.pb(-(++n));
//                cout<<"EDGE "<<nc.back()<<' '<<cur[j]<<' '<<cur[j+1]<<endl;
                x.pb(cur[j]);y.pb(cur[j+1]);
                curt.pb(0);
            }
            cur=nc;
            --lvl;
        }
        reverse(all(goes[i]));
        lvl=lt;
//        if(i==4){
//            i=4;
//        }
        while(sz(goes[i])!=pw(lvl)) goes[i].pb(cur.back());
        while(sz(goes[i])){
            int v=cur.back();
            while(1){
                v=-v;
//                cout<<"V "<<v<<' '<<sz(x)<<endl;
                int &u=(curt[v-1]?y[v-1]:x[v-1]);
                curt[v-1]^=1;
                if(u>=0){
                    u=goes[i].back(),goes[i].pop_back();
                    break;
                }
                v=u;
            }
        }
        c[i]=cur.back();
    }
    c[0]=a[0];
//        cout<<sz(c)<<' '<<sz(x)<<' '<<sz(y)<<endl;
//    for(auto &z : c)
//        cout<<z<<' ';
//    cout<<endl;
//    for(int i=0;i<sz(x);i++){
//        if(x[i]==y[i]){
//
//        }
//    }
//        cout<<x[i]<<' '<<y[i]<<endl;

    answer(c, x, y);
}

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