Submission #587737

#	Time	Username	Problem	Language	Result	Execution time	Memory
587737		alirezasamimi100	Mechanical Doll (IOI18_doll)	C++17	100 / 100	102 ms	10988 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

vector<int> X,Y,A;
int N;

int solve(int k, int j){
    int v=-(int)X.size()-1;
    if(A[(((N-1)>>j)<<j)+k]==-1){
        return -1;
    }
    if((1<<j)==N){
        return A[k];
    }
    X.pb(0);
    Y.pb(0);
    int x=solve(k,j+1),y=solve(k+(1<<j),j+1);
    X[-v-1]=x;
    Y[-v-1]=y;
    return v;
}


void create_circuit(int M, vector<int> wtf) {
    vector<int> C(M + 1, -2);
    if((int)wtf.size()==1){
        C[0]=wtf[0];
        C[wtf[0]]=0;
        answer(C,X,Y);
        return;
    }
    wtf.pb(0);
    C[0]=wtf[0];
    wtf.erase(wtf.begin());
    N = wtf.size();
    int x=1,p=0;
    while(x<N) x*=2,p++;
    vector<int> vec;
    for(int i=0; i<p; i++){
        if((x-N)>>i&1) vec.pb(i);
    }
    reverse(vec.begin(),vec.end());
    A.resize(x,0);
    int k=0,t=0;
    for(int i : vec){
        for(int j=0; j<(1<<i); j++){
            A[(j<<(p-i))|k]=-1;
        }
        k|=1<<(p-i-1);
    }
    N=x;
    for(int i=0; i<N; i++){
        if(A[i]==-1) continue;
        A[i]=wtf[t++];
    }
    X.pb(-1);
    Y.pb(-2);
    solve(0,0);
    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: 56 / 56