Submission #92077

#	Time	Username	Problem	Language	Result	Execution time	Memory
92077		Retro3014	Mechanical Doll (IOI18_doll)	C++17	100 / 100	169 ms	11172 KiB

doll

#include "doll.h"
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> X, Y;
vector<int> type;
int N, K;

int idx(int x){
    return -x-1;
}

void dfs(int x, int y){
    int k=y/2;
    if(K-k >= N){
        K-=k;
        X[idx(x)]=-1;
    }else{
        if(k==1){
            X[idx(x)]=0;
        }
        else{
            X[idx(x)]=-((int)X.size()+1);
            X.push_back(0); Y.push_back(0); type.push_back(0);
        }
    }
    if(k==1){
        Y[idx(x)]=0;
    }else{
        Y[idx(x)]=-((int)X.size()+1);
        X.push_back(0); Y.push_back(0); type.push_back(0);
    }
    if(X[idx(x)]!=0 && X[idx(x)]!=-1)    dfs(X[idx(x)], k);
    if(Y[idx(x)]!=0 && Y[idx(x)]!=-1)    dfs(Y[idx(x)], k);
}

void dfs2(int x, int y){
    if(type[idx(x)]==0){
        type[idx(x)]=1;
        if(X[idx(x)]==0){
            X[idx(x)]=y;
            return;
        }else{
            dfs2(X[idx(x)], y);
            return;
        }
        
    }else{
        type[idx(x)]=0;
        if(Y[idx(x)]==0){
            Y[idx(x)]=y;
            return;
        }else{
            dfs2(Y[idx(x)], y);
            return;
        }
    }
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    N = (int)A.size();
    int two=1; while(two<N) two*=2;
    K = two;
    if(N==1){
        vector<int> C(M+1);
        C[0]=A[0];
        for(int i=1; i<=M; i++){
            C[i]=0;
        }
        vector<int> XY(0);
        answer(C, XY, XY);
        return;
    }
    X.push_back(0); Y.push_back(0); type.push_back(0);
    dfs(-1, two);
    for(int i=0; i<N; i++){
        dfs2(-1, A[i]);
    }
    vector<int> C(M+1);
    for(int i=0; i<=M; i++){
        C[i]=-1;
    }
    answer(C, X, Y);
    return;
}

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