Submission #75241

#	Time	Username	Problem	Language	Result	Execution time	Memory
75241		mammamia	Mechanical Doll (IOI18_doll)	C++14	53 / 100	182 ms	18056 KiB

doll

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

vector<vector<int>> switches;
vector<pair<int, int> > leaves;

int swcnt = 0;
void rec(int root, int h){

    // binary tree
    for (int i = 0; i < 2; ++i) {
        if (h == 1) {
            leaves.push_back({root, i});
        } else {
            swcnt++;
            switches[i][root - 1] = -swcnt;
            rec(swcnt, h - 1);
        }
    }
}

void create_circuit(int M, vector<int> A) {

    int N = A.size();
    vector<vector<int>> G(M+1, vector<int>());

    for(int i=0; i<N; ++i){
        if(i == N - 1){
            G[A[i]].push_back(0);
        } else {
            G[A[i]].push_back(A[i+1]);
        }
    }

    // compute the log2
    vector<int> l2(N+1, 0);
    l2[1] = 0;
    for(int i=2; i<N+1; ++i)
        l2[i] = l2[(i+1)/2] + 1;


    int totalSwitches = 0;
    for(int i=1; i<=M; ++i){
        if(G[i].size() > 1){
            totalSwitches += 2*(1<<(l2[G[i].size()] - 1)) - 1;
        }
    }

    vector<int> C = vector<int>(M+1, 0);
    switches = vector<vector<int>>(2, vector<int>(totalSwitches, 0));

    C[0] = A[0];

    for(int i=1; i<=M; ++i){

        // dumb connection
        if(G[i].size() == 0){
            C[i] = i;
            continue;
        }

        //connect with the next one
        if(G[i].size() == 1){
            C[i] = G[i][0];
            continue;
        }

        swcnt++;
        C[i] = -swcnt;
        int switchRoot = C[i];

        // build the switch tree and get the leaves
        leaves.clear();
        int height = l2[G[i].size()];
        rec(-C[i], height);

        // save the last element to swap later
        int lstp = 0;

        for(int it = 0; it < (1<<height); ++it) {

            int rev = 0;
            int aux = it;
            int bt = height - 1;

            // reverse bits
            while(aux){
                if(aux&1)
                    rev |= (1<<bt);
                aux/=2;
                bt--;
            }

            int lf = leaves[rev].first;
            int ls = leaves[rev].second;

            if (it < G[i].size()) {
                switches[ls][lf - 1] = G[i][it];
                lstp = rev;
            } else {
                switches[ls][lf - 1] = switchRoot;
            }
        }
        if(G[i].size() < (1<<height)) {
            swap(switches[leaves[lstp].second][leaves[lstp].first - 1],
                 switches[1][leaves[leaves.size() - 1].first - 1]);
        }
    }

    /*
    for(auto el: C){
        cout<<el<<" ";
    }
    cout<<"\n";
    for(auto el: X){
        cout<<el<<" ";
    }
    cout<<"\n";
    for(auto el: Y){
        cout<<el<<" ";
    }
    cout<<"\n";
     */
    answer(C, switches[0], switches[1]);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             if (it < G[i].size()) {
      |                 ~~~^~~~~~~~~~~~~
doll.cpp:106:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |         if(G[i].size() < (1<<height)) {
      |            ~~~~~~~~~~~~^~~~~~~~~~~~~

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