Submission #75058

#	Time	Username	Problem	Language	Result	Execution time	Memory
75058		dacin21	Mechanical Doll (IOI18_doll)	C++14	100 / 100	143 ms	12400 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

int bit_mirror(int A, int digits){
    int ret = 0;
    while(digits--){
        ret = ret<<1 | (A&1);
        A>>=1;
    }
    return ret;
}

void create_circuit(int M, vector<int> A){
    const int lgn = __lg(2*A.size()-1);
    const int N = 1<<lgn;
    assert(N/2 < A.size() && A.size() <= N);
    // remove surplus subtrees
    vector<char> dead(2*N, 0);
    int m = N - A.size();
    for(int i=lgn, j=1;i>=0;--i,j=2*j){
        if((m>>i)&1){
            dead[j] = 1;
            ++j;
        }
    }
    for(int i=1;i<N;++i){
        if(dead[i]){
            dead[2*i] = dead[2*i+1] = 1;
        }
    }
    // assign leaves
    A.push_back(0);
    vector<int> leaves(N, -1);
    for(int i=0, k=0;i<N;++i){
        int j = bit_mirror(i, lgn);
        if(!dead[N+j]){
            leaves[j] = A[++k];
        }
        //cerr << i << " -> " << j << "\n";
    }
    // compress
    vector<int> id(2*N, -1);
    for(int i=2, j=-2;i<N;++i){
        if(!dead[i]){
            id[i] = j--;
        }
    }
    for(int i=0;i<N;++i){
        id[N+i] = leaves[i];
    }

    vector<int> C(M+1, 0);
    C[0] = A[0];
    for(int i=1;i<=M;++i){
        C[i] = -1;
    }
    const int K = -*min_element(id.begin(), id.end());
    vector<int> X(K), Y(K);
    for(int i=0;i<N;++i){
        if(!dead[i]){
            X[-id[i]-1] = id[2*i];
            Y[-id[i]-1] = id[2*i+1];
        }
    }
    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 function 'void create_circuit(int, std::vector<int>)':
doll.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     assert(N/2 < A.size() && A.size() <= N);
      |            ~~~~^~~~~~~~~~
doll.cpp:17:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   17 |     assert(N/2 < A.size() && A.size() <= N);
      |                              ~~~~~~~~~^~~~

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