Submission #1210641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210641		Aviansh	Mechanical Doll (IOI18_doll)	C++20	66.61 / 100	88 ms	13424 KiB

doll

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

using namespace std;
int n;
int cn;
vector<int>x;
vector<int>y;

vector<int>normalize(vector<int>arr){
    vector<int>temp;
    vector<int>buff;
    for(int i : arr){
        if(i!=-1){
            temp.push_back(i);
        }
        else{
            buff.push_back(i);
        }
    }
    if(temp.size()==0){
        //all -1s
        return {-1};
    }
    vector<int>ans;
    int i = 0;
    int j = 0;
    for(int z = 0;z<arr.size();z++){
        if(j<buff.size()){
            ans.push_back(buff[j]);
            j++;
        }
        if(i<temp.size()){
            ans.push_back(temp[i]);
            i++;
        }
    }
    return ans;
}

int create(vector<int>req){
    set<int>s;
    for(int i : req){
        s.insert(i);
        if(s.size()>=2){
            break;
        }
    }
    if(s.size()==1){
        return {req[0]};
    }
    if(req.size()==1){
        return req[0];
    }
    cn--;
    int curr = cn;
    vector<int>reqx,reqy;
    for(int i = 0;i<req.size();i++){
        if(i%2){
            reqy.push_back(req[i]);
        }
        else{
            reqx.push_back(req[i]);
        }
    }
    if(reqx.size()!=reqy.size()){
        reqy.push_back(reqx[reqx.size()-1]);
        reqx[reqx.size()-1]=curr;
    }
    x.push_back(-1e9);
    y.push_back(-1e9);
    int retx = create(reqx);
    x[-curr-1]=retx;
    int rety = create(reqy);
    y[-curr-1]=rety;
    return curr;
}

void create_circuit(int m, vector<int> a) {
    vector<int>c(m+1);
    n=a.size();
    while(__builtin_popcount((int)a.size()+1)!=1){
        a.push_back(-1);
    }
    a.push_back(0);
    a=normalize(a);
    cn=0;
    x.clear();
    y.clear();
    int node = create(a);
    for(int i = 0;i<=m;i++){
        c[i]=node;
    }
    answer(c,x,y);
}

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