Submission #885718

#	Time	Username	Problem	Language	Result	Execution time	Memory
885718		JakobZorz	Mechanical Doll (IOI18_doll)	C++17	53 / 100	134 ms	18048 KiB

doll

#include"doll.h"
#include<iostream>
#include<algorithm>
using namespace std;

vector<int>sx,sy;
vector<int>arr;

int new_switch(){
    sx.push_back(0);
    sy.push_back(0);
    return(int)sx.size()-1;
}

pair<vector<int>,vector<int>>split(vector<int>vec){
    pair<vector<int>,vector<int>>res;
    for(int i=0;i<vec.size();i++){
        if(i%2==0)
            res.first.push_back(vec[i]);
        else
            res.second.push_back(vec[i]);
    }
    return res;
}

int build(vector<int>exits){
    int root=new_switch();
    
    if(exits.size()==2){
        sx[root]=exits[0];
        sy[root]=exits[1];
        return -root-1;
    }
    
    pair<vector<int>,vector<int>>res=split(exits);
    sx[root]=build(res.first);
    sy[root]=build(res.second);
    
    return -root-1;
}

int handle(vector<int>exits){
    if(exits.size()==0)
        return 0;
    
    if(exits.size()==1)
        return exits[0];
    
    reverse(exits.begin(),exits.end());
    int pow2=1;
    while(pow2<(int)exits.size())
        pow2*=2;
    int root=new_switch();
    while(exits.size()<pow2)
        exits.push_back(-root-1);
    reverse(exits.begin(),exits.end());
    
    if(exits.size()==2){
        sx[root]=exits[0];
        sy[root]=exits[1];
        return -root-1;
    }
    
    pair<vector<int>,vector<int>>res=split(exits);
    sx[root]=build(res.first);
    sy[root]=build(res.second);
    
    return -root-1;
}

void create_circuit(int m,vector<int>_arr){
    arr=_arr;
    int n=(int)arr.size();
    vector<vector<int>>occ(m+1);
    for(int i=0;i<n;i++)
        occ[arr[i]].push_back(i);
    
    vector<int>ans(m+1);
    ans[0]=arr[0];
    
    for(int i=1;i<=m;i++){
        vector<int>exits;
        for(int j:occ[i]){
            if(j==n-1)
                exits.push_back(0);
            else
                exits.push_back(arr[j+1]);
        }
        /*cout<<i<<": ";
        for(int i:occ[i])
            cout<<i<<" ";
        cout<<"\n";*/
        ans[i]=handle(exits);
    }
    
    answer(ans,sx,sy);
}

Compilation message (stderr)

doll.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > split(std::vector<int>)':
doll.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<vec.size();i++){
      |                 ~^~~~~~~~~~~
doll.cpp: In function 'int handle(std::vector<int>)':
doll.cpp:54:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     while(exits.size()<pow2)
      |           ~~~~~~~~~~~~^~~~~

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