Submission #297497

#	Time	Username	Problem	Language	Result	Execution time	Memory
297497		eohomegrownapps	Mechanical Doll (IOI18_doll)	C++14	12.33 / 100	117 ms	10128 KiB

doll

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

vector<vector<int>> adjlist;

vector<int> exitto;
vector<int> switchxto;
vector<int> switchyto;

int sind = 0;

// level 0 -- base

//int lind = -1;
int finale = 0;

int create(int parent, int level, int num, const vector<int> &seq, int s, int e){
    // returns index of switch
    /*cout<<"make switch "<<-1-sind<<" at level "<<level<<'\n';
    for (int i : seq){
        cout<<i<<' ';
    }cout<<'\n';
    cout<<seq.size()<<'\n';*/
    if (num==0){
        if (level==0){
            return (e==finale)?0:-1;
        }
        // make something that counts (1<<level) times before returning
        int firstswitch = sind;
        for (int i = 0; i<level-1; i++){
            // make switch
            // parent: prevconnect
            // x: -1
            // y: sind+1
            switchxto.push_back(1e9);
            switchyto.push_back(1e9);
            switchxto[sind]=-1;
            switchyto[sind]=-1-(sind+1);
            sind++;
        }
        switchxto.push_back(1e9);
        switchyto.push_back(1e9);
        switchxto[sind]=-1;
        switchyto[sind]=(e==finale)?0:-1;
        //lind=sind;
        sind++;
        return -1-firstswitch;
    }
    if (level==0){
        //numleft--;
        return seq[0];
    }

    int switchtouse = sind;
    switchxto.push_back(1e9);
    switchyto.push_back(1e9);
    sind++;

    int sendleft = min((1<<(level-1)),num);
    int sendright = max(0,num-(1<<(level-1)));
    vector<int> left;
    vector<int> right;
    
    int ptr = 0;
    for (int i = 0; i<sendright; i++){
        left.push_back(seq[ptr]);
        right.push_back(seq[ptr+1]);
        ptr+=2;
    }
    for (int i = sendright; i<sendleft; i++){
        left.push_back(seq[ptr]);
        ptr++;
    }

    int cl = create(switchtouse,level-1,sendleft,left,s,(s+e)/2);
    int cr = create(switchtouse,level-1,sendright,right,(s+e)/2+1,e);
    switchxto[switchtouse]=cl;
    switchyto[switchtouse]=cr;
    return -1-switchtouse;
}

void create_circuit(int m, std::vector<int> a) {
    int n = a.size();

    if (n%2!=1){
        a.push_back(-1);
    }
    n=a.size();
    int level = log2(n-1)+1;
    finale = (1<<level)-1;
    create(0,level,n,a,0,(1<<level)-1);
    /*if (lind!=-1){
        switchyto[lind]=0;
    }*/
    exitto.resize(m+1,-1);
    /*for (int i : switchxto){
        cout<<i<<' ';
    }cout<<'\n';
    for (int i : switchyto){
        cout<<i<<' ';
    }cout<<'\n';*/
    answer(exitto,switchxto,switchyto);
}

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