Submission #615981

#	Time	Username	Problem	Language	Result	Execution time	Memory
615981		neki	Mechanical Doll (IOI18_doll)	C++14	100 / 100	116 ms	10768 KiB

doll

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

using namespace std;

/*void answer(vc<int> c, vc<int> x, vc<int> y){
    for(auto v: c) cout << v << " ";cout << endl;
    for(auto v: x) cout << v << " ";cout << endl;
    for(auto v: y) cout << v << " ";cout << endl;
}*/

int rev(int x, const int k){
    int ret=0;
    for(int i=0;i<k;++i) if(x&(1<<i)) ret+=(1<<(k-i-1));
    return ret;
}

void create_circuit(int m, vc<int> a){
    a.push_back(0);
    
    int k=0;
    while(a.size()>(1<<k)) ++k;
    int zac=(1<<k) -(int) a.size();
    
    //cout << zac << " "<< k <<" " << a.size() << endl;
    
    vc<int> x, y;
    int cnt=0;
    vc<pair<int, int>> red(1<<k, make_pair(-1, -1));
    int bla=0;
    function<int (int, int)> solve=[&](int l, int r){
        int mojid=++cnt;
        int mid=(l+r)/2;
        x.push_back(INT_MAX), y.push_back(INT_MAX);
        
        if(r-l==2){
            if(l>=zac)  red[rev(l, k)]=make_pair(mojid-1, 0);
            else x[mojid-1]=-1;
            red[rev(l+1, k)]=make_pair(mojid-1, 1);
        }
        else{
            if(mid<=zac)  x[mojid-1]=-1;
            else x[mojid-1]=-solve(l, mid);
            y[mojid-1]=-solve(mid, r);
        }
        return mojid;
    };
    solve(0, 1<<k);
    
    for(int i=0, cur=0;i<(1<<k);++i) if(red[i]!=make_pair(-1, -1)){
        //cout << red[i].first << " ";
        if(red[i].second==0) x[red[i].first]=a[cur++];
        if(red[i].second==1) y[red[i].first]=a[cur++];
        //cout << cur << " ";
    }
    //cout << endl;
    
    answer(vc<int>(m+1, -1), x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:23:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     while(a.size()>(1<<k)) ++k;
      |           ~~~~~~~~^~~~~~~
doll.cpp:31:9: warning: unused variable 'bla' [-Wunused-variable]
   31 |     int bla=0;
      |         ^~~

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