Submission #885731

#	Time	Username	Problem	Language	Result	Execution time	Memory
885731		JakobZorz	Mechanical Doll (IOI18_doll)	C++17	37 / 100	117 ms	13344 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){
    if(exits.size()==1)
        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;
    while(exits.size()<pow2)
        exits.push_back(-1);
    reverse(exits.begin(),exits.end());
    
    int root=build(exits);
    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:51:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     while(exits.size()<pow2)
      |           ~~~~~~~~~~~~^~~~~
doll.cpp:41:9: warning: unused variable 'n' [-Wunused-variable]
   41 |     int n=(int)arr.size();
      |         ^

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