Submission #341329

#	Time	Username	Problem	Language	Result	Execution time	Memory
341329		blue	Mechanical Doll (IOI18_doll)	C++11	9 / 100	89 ms	8408 KiB

doll

#include "doll.h"
#include <vector>
#include <iostream>
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';

    for(int i = tree_size + 1; i <= tree_size + 2*last_row_size; i++)
    {
        // cout << "switch = " << i << '\n';
        if(i - tree_size < trigger_seq.size())
        {
            if((i - tree_size) % 2 == 1) switch_left_exit[i/2 -1] = trigger_seq[i - tree_size + 1 -1];
            else switch_right_exit[i/2 -1] = trigger_seq[i - tree_size + 1 -1];
        }
        else if(i == (tree_size + 2*last_row_size))
        {
            switch_right_exit[i/2 -1] = 0;
        }
        else
        {
            if((i - tree_size) % 2 == 1) switch_left_exit[i/2 -1] = -1;
            else switch_right_exit[i/2 -1] = -1;
        }
    }

    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:36:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     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:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         if(i - tree_size < trigger_seq.size())
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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