Submission #1034682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034682		Ludissey	Mechanical Doll (IOI18_doll)	C++14	85.55 / 100	65 ms	12660 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
using namespace std;

void create_circuit(int M, std::vector<int> A){
    int N=sz(A);
    vector<int> C(M+1,0);
    vector<vector<int>> nxt(M+1);
    vector<int> X;
    vector<int> Y;
    for (int i = 1; i < N; i++)
    {
        nxt[A[i-1]].push_back(A[i]);
    }
    nxt[A[N-1]].push_back(0);
    C[0]=A[0];
    int trig=-1;
    for (int nx = 1; nx <= M; nx++)
    {
        if(sz(nxt[nx])==0) continue;
        if(sz(nxt[nx])<=1){
            C[nx]=nxt[nx][0];
        }else if(sz(nxt[nx])<=2){
            C[nx]=trig;
            trig--;
            X.push_back(nxt[nx][0]);
            Y.push_back(nxt[nx][1]);
        }else if(sz(nxt[nx])==3){
            C[nx]=trig;
            X.push_back(trig-1);
            Y.push_back(trig-2);
            X.push_back(nxt[nx][0]);
            Y.push_back(trig);
            X.push_back(nxt[nx][1]);
            Y.push_back(nxt[nx][2]);
            trig-=3;
        } 
        else if(sz(nxt[nx])==4){
            C[nx]=trig;
            X.push_back(trig-1);
            Y.push_back(trig-2);
            X.push_back(nxt[nx][0]);
            Y.push_back(nxt[nx][2]);
            X.push_back(nxt[nx][1]);
            Y.push_back(nxt[nx][3]);
            trig-=3;
        }
        else{
            int origTRIG=trig;
            C[nx]=trig;
            int logo=log2(sz(nxt[nx])*2-1);
            vector<pair<int,int>> S(logo);
            int diff=(1<<logo)-sz(nxt[nx]);
            int inventedTRIG=-1;
            int res=sz(nxt[nx]);
            while(res>0){

            }
            for (int j = 0; j < logo; j++)
            {
                if(diff&(1<<((logo-1)-j))) S[j].first=inventedTRIG;
                else S[j].first=1;
                if(j==logo-1) S[j].second=nxt[nx].back();
                else S[j].second=(inventedTRIG-1)-j;
            }

            trig--;
            vector<vector<int>> has(logo);
            vector<bool> state(logo);
            int c=0;
            int pos=-1;
            while(c<sz(nxt[nx])){
                if(state[(-pos)-1]){
                    state[(-pos)-1]=false;
                    if(-S[(-pos)-1].second<=0) {
                        has[(-pos)-1].push_back(nxt[nx][c]);
                        c++;
                        pos=-1;
                    }else{
                        pos=S[(-pos)-1].second;
                    }
                }else {
                    state[(-pos)-1]=true;
                    if(-S[(-pos)-1].first<=0) {
                        has[(-pos)-1].push_back(nxt[nx][c]);
                        c++;
                        pos=-1;
                    }
                    else{
                        pos=S[(-pos)-1].first;
                    }
                }
            }
            for (int j = 0; j < logo; j++)
            {
                int torem=sz(Y);
                int inv=((logo-1)-j);
                if(diff&(1<<inv)) {
                    if(inv==0){
                        X.push_back(origTRIG);
                        Y.push_back(has[j][0]);
                    }else{
                        X.push_back(origTRIG);
                        Y.push_back(trig); trig--;
                    }
                    continue;
                }
                if(inv==0){
                    X.push_back(has[j][0]);
                    Y.push_back(has[j][1]);
                    continue;
                }
                Y.push_back(origTRIG);
                X.push_back(trig); trig--;
                

                int c2=0;
                for (int i = 0; i < (1<<(inv-1))-1; i++)
                {
                    X.push_back(trig-c2);
                    Y.push_back(trig-(c2+1));
                    c2+=2;
                }
                trig-=c2;
                vector<int> S2(sz(has[j]));
                for (int i = 0; i < sz(has[j]); i++)
                {
                    int _i=i+1; 
                    int pos2=0;
                    int cPOW=0;
                    for (int k = inv-1; k >=0; k--)
                    {
                        if(_i>(1<<k)){
                            pos2+=(1<<cPOW);
                            _i-=(1<<k);
                        }
                        cPOW++;
                    }
                    S2[pos2]=has[j][i];
                }
                for (int i = 0; i < sz(S2); i++)
                {
                    if(i%2==0) X.push_back(S2[i]);
                    else Y.push_back(S2[i]);
                }
                Y[torem]=trig; trig--;
            }
        }
    }
    for (int i = 0; i <= M; i++)
    {
        // << C[i] << " ";
    }
    //cerr<<"\n";
    for (int i = 0; i < sz(X); i++){
        //cerr << X[i] << " " << Y[i] << "\n";
    }

    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.5530038336 / 56