Submission #341345

#	Time	Username	Problem	Language	Result	Execution time	Memory
341345		blue	Mechanical Doll (IOI18_doll)	C++11	47 / 100	286 ms	9452 KiB

doll

#include "doll.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

// void answer(vector<int> C, vector<int> X, vector<int> Y)
// {
//     cout << C.size() << ' ' << X.size() << '\n';
//     for(int i = 0; i < C.size(); i++) cout << C[i] << '\n';
//     for(int i = 0; i < X.size(); i++) cout << X[i] << ' ' << Y[i] << '\n';
// }


void create_circuit(int num_triggers, vector<int> trigger_seq)
{
    int origin = 0;
    int root = -1;

    vector<int> trigger_exit(num_triggers +1, root);
    vector<int> switch_left_exit, switch_right_exit;


    trigger_exit[ origin ] = trigger_seq[0];

    if(trigger_seq.size() == 1)
    {
        trigger_exit = vector<int>(num_triggers +1, 0);
        answer(trigger_exit, switch_left_exit, switch_right_exit);
        return;
    }

    trigger_exit[ trigger_seq[0] ] = root; //unnecessary

    int last_row_pow;

    for(last_row_pow = 0; 2*(1 << last_row_pow) < trigger_seq.size(); last_row_pow++); //1<<p is the size of the last row of the binary tree
                                    //2*(1<<p) = 1<<(p+1) <= N < (1<<p+2)

    int last_row_size = (1 << last_row_pow);
    int tree_size = 2 * last_row_size - 1;

    // cout << last_row_size << ' ' << tree_size << '\n';

    switch_left_exit = vector<int>( tree_size , root); //2*last_row_size because binary tree
    switch_right_exit = vector<int>( tree_size , root);

    for(int i = 1; i <= tree_size - last_row_size; i++)
    {
        switch_left_exit[i -1] = -2*i;
        switch_right_exit[i -1] = -(2*i + 1);
    }

    // cout << "0 " << C[0] << '\n';
    // for(int i = 1; i < (1 << (p+1)); i++) cout << i << ' ' << X[i-1] << ' ' << Y[i-1] << '\n';

    vector<int> invert_order(2*last_row_size);
    for(int i = 0; i < 2*last_row_size; i++) invert_order[i] = i;
    // for(int g: invert_order) cout << g << ' ';
    // cout << '\n';

    sort(invert_order.begin(), invert_order.end(), [] (int x, int y)
    {
        for(int bit = 0; bit <= 20; bit++)
        {
            if(    (x & (1 << bit)) < (y & (1 << bit))    ) return 1;
            if(    (x & (1 << bit)) > (y & (1 << bit))    ) return 0;
        }
        return 0;
    });

    // for(int g: invert_order) cout << g << ' ';
    // cout << '\n';

    for(int i = 1; i < trigger_seq.size(); i++)
    {
        int tree_row_pos = tree_size + 1 + invert_order[i-1];
            // cout << "i = " << i << ' ' << tree_row_pos << '\n';

        if((tree_row_pos - tree_size) % 2 == 1)
            switch_left_exit[tree_row_pos/2 -1] = trigger_seq[i];
        else switch_right_exit[tree_row_pos/2 -1] = trigger_seq[i];
    }
    switch_right_exit[tree_size -1] = 0;


    answer(trigger_exit, switch_left_exit, switch_right_exit);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:37:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(last_row_pow = 0; 2*(1 << last_row_pow) < trigger_seq.size(); last_row_pow++); //1<<p is the size of the last row of the binary tree
      |                           ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
doll.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 1; i < trigger_seq.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~

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