Submission #1016660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016660		Unforgettablepl	Mechanical Doll (IOI18_doll)	C++17	100 / 100	117 ms	13532 KiB

doll

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

void answer(vector<int> C, vector<int> X, vector<int> Y);

int reverse_bits(int x){
    int res = 0;
    for(int bit=0;bit<=20;bit++)if(x&(1<<bit))res|=1<<(30-bit);
    return res;
}

void create_circuit(int M, vector<int> A) {    
    int N = A.size();
    vector<int> C(M + 1,-1);C[0]=A[0];
    vector<int> X(400001),Y(400001);
    vector<int> nextoccurences = A;
    nextoccurences.erase(nextoccurences.begin());
    nextoccurences.emplace_back(0);
    vector<int> perm;
    {
        vector<pair<int,int>> elements;
        int siz = 2;
        while(nextoccurences.size()>siz)siz<<=1;
        int tar = siz-N;
        vector<bool> taken(siz);
        for(int i=0;i<siz;i++)elements.emplace_back(reverse_bits(i),i);
        sort(elements.begin(),elements.end());
        for(int i=0;i<tar;i++)taken[elements[i].second]=true;
        auto iter = nextoccurences.begin();
        for(int i=0;i<siz;i++){
            if(taken[i])perm.emplace_back(-1);
            else perm.emplace_back(*(iter++));
        }
    }
    int S = 1;
    function<void(int,vector<int>)> calc = [&](int x,vector<int> targets){
        if(targets.size()==2){
            X[x] = targets[0];
            Y[x] = targets[1];
        } else {
            vector<int> odds;
            vector<int> evens;
            for(int i=0;i<targets.size();i++)
                if(i&1)odds.emplace_back(targets[i]);
                else evens.emplace_back(targets[i]);
            bool Xworks = false;
            for(int&i:evens)if(i!=-1)Xworks=true;
            bool Yworks = false;
            for(int&i:odds)if(i!=-1)Yworks=true;
            if(Xworks){
                X[x] = -(++S);
                calc(S,evens);
            } else {
                X[x] = -1;
            }
            if(Yworks){
                Y[x] = -(++S);
                calc(S,odds);
            } else {
                Y[x] = -1;
            }
        }
    };
    calc(1,perm);
    X.erase(X.begin());
    Y.erase(Y.begin());
    X.resize(S);
    Y.resize(S);
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:23:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |         while(nextoccurences.size()>siz)siz<<=1;
      |               ~~~~~~~~~~~~~~~~~~~~~^~~~
doll.cpp: In lambda function:
doll.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int i=0;i<targets.size();i++)
      |                         ~^~~~~~~~~~~~~~~

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