Submission #612425

#	Time	Username	Problem	Language	Result	Execution time	Memory
612425		neki	Mechanical Doll (IOI18_doll)	C++14	28 / 100	96 ms	9696 KiB

doll

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

using namespace std;

void create_circuit(int m, vc<int> a){
    a.push_back(0);
    int k=a.size();
    while(k != (1<< __builtin_ctz(k))) ++k;
    
    vc<int> c(m+1), x, y;
    c[0]=-1;
    
    int id=1;
    function<int (int, int, vc<int>)> solve=[&](int l, int r, vc<int> arr){
        assert(arr.size());
        
        int mojid=id++;
        x.push_back(INT_MAX), y.push_back(INT_MAX);
        
        int len=(r-l), mid=(l+r)/2;
        int vd=min(len/2, (int)arr.size());
        int vl=arr.size()-vd;assert(vl>=0 and vl<arr.size());
        int pl=len/2-vl, pr=len/2-vd;
        //cout << vd << " " << vl << endl;
        
        vc<int> lev, des;
        for(int i=0, komu=0;i<arr.size();++i){
            if(pl) --pl, des.push_back(arr[i]);
            else{
                if(komu==0) lev.push_back(arr[i]);
                else des.push_back(arr[i]);
                komu= !komu;
            }
        }
        /*cout << mojid << ": "<<endl;
        for(auto v: lev) cout << v <<" "; cout << endl;
        for(auto v: des) cout << v <<" "; cout << endl;*/
        
        assert(len>=2);
        assert(des.size());
        if(len==2){
            if(lev.size()){
                assert(lev.size()==1);
                x[mojid-1]=lev[0];
                if(lev[0]!=0) c[lev[0]]=-1;
            }
            else x[mojid-1]=-1;
            
            if(des.size()){
                assert(des.size()==1);
                y[mojid-1]=des[0];
                if(des[0]!=0) c[des[0]]=-1;
            }
        }
        else{
            if(lev.size()) x[mojid-1]=-solve(l, mid, lev);
            else x[mojid-1]=-1;
            
            y[mojid-1]=-solve(mid, r, des);
        }
        
        return mojid;
    };
    solve(0, k, a);
    
    //for(auto v: c) cout << v << " ";cout << endl;
    //for(auto v: x) cout << v << " ";cout << endl;
    //for(auto v: y) cout << v << " ";cout << endl;
    
    answer(c, x, y);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from doll.cpp:2:
doll.cpp: In lambda function:
doll.cpp:24:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         int vl=arr.size()-vd;assert(vl>=0 and vl<arr.size());
      |                                               ~~^~~~~~~~~~~
doll.cpp:29:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i=0, komu=0;i<arr.size();++i){
      |                             ~^~~~~~~~~~~
doll.cpp:25:26: warning: unused variable 'pr' [-Wunused-variable]
   25 |         int pl=len/2-vl, pr=len/2-vd;
      |                          ^~

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