Submission #885753

#	Time	Username	Problem	Language	Result	Execution time	Memory
885753		JakobZorz	Mechanical Doll (IOI18_doll)	C++17	100 / 100	133 ms	13328 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;
}

vector<int>get_cancelled(int size,int cancelled){
    if(size==1&&cancelled==0)
        return{0};
    if(size==1&&cancelled==1)
        return{-1};
    
    vector<int>vec1=get_cancelled(size/2,min(cancelled,size/2));
    vector<int>vec2=get_cancelled(size/2,max(cancelled-size/2,0));
    vector<int>vec;
    for(int i=0;i<size/2;i++){
        vec.push_back(vec1[i]);
        vec.push_back(vec2[i]);
    }
    return vec;
}

int build(vector<int>exits){
    bool all_same=true;
    for(int i=0;i<(int)exits.size()-1;i++)
        if(exits[i]!=exits[i+1])
            all_same=false;
    
    if(all_same)
        return exits[0];
    
    int root=new_switch();
    
    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<int>ans(m+1);
    
    vector<int>exits=arr;
    exits.push_back(0);
    reverse(exits.begin(),exits.end());
    int pow2=1;
    while(pow2<(int)exits.size())
        pow2*=2;
    
    vector<int>exits2=get_cancelled(pow2,pow2-(int)exits.size());
    for(int&i:exits2){
        if(i==0){
            i=exits.back();
            exits.pop_back();
        }
    }
    
    
    int root=build(exits2);
    for(int&i:ans)
        i=root;
    
    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 'void create_circuit(int, std::vector<int>)':
doll.cpp:62:9: warning: unused variable 'n' [-Wunused-variable]
   62 |     int n=(int)arr.size();
      |         ^

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