Submission #1241782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241782		Adriano	Mechanical Doll (IOI18_doll)	C++17	100 / 100	72 ms	11316 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>

using namespace std;

vector<int> C, X, Y, state;
int s_count = 0;

void simulate_and_form(int &idx, const int original_count, int &left, const vector<int> &d_adj, const int &root, int &offset)
{

    int count = original_count;

    while ( offset < d_adj.size() )
    {
        if ( root == idx )
            count = original_count;

        if (-idx > s_count)
        {
            ++s_count;
            X.push_back(0), Y.push_back(0), state.push_back(0);
        }
        state[-idx - 1] = !state[-idx - 1];

        // When X
        if( state[-idx - 1] ) //                    State is X or Y
        {
            if ( 0 == X[-idx - 1] ) //              Is X for this idx defined? 
            {
                if ( count/2 <= left ) //             Unnecesary switch?
                {
                    X[-idx - 1] = root;
                    left -= count/2;
                    idx = root, count = original_count;
                    continue;
                }
                else if ( 1 == count/2 ) //           Leaf?
                {
                    X[-idx - 1] = d_adj[offset++];
                    idx = root;
                    continue;
                }
                else //                             Just continue down
                {
                    X[-idx - 1] = -s_count - 1;
                }
            }
            if ( 2 < count )
                idx = X[-idx - 1], count /= 2; // This will simulate going down
            else
                idx = root;
        }


        // When Y
        else
        {
            if ( 0 == Y[-idx - 1] ) //              Is Y for this idx defined?
            {
                if ( 1 == count/2 ) //                Leaf?
                {
                    Y[-idx - 1] = d_adj[offset++];
                    idx = root, count = original_count;
                    continue;
                }   
                else //                             Just continue down
                    Y[-idx - 1] = -s_count - 1;
            }
            if ( 2 < count )
                idx = Y[-idx - 1], count /= 2; // Same as in if above
            else
                idx = root, count = original_count;
        }
    }
    return;
}

void create_circuit(int M, vector<int> A)
{
    vector< vector<int> > directed_adj(M+1);
    C.assign(M+1, -1);
    A.push_back(0);

    int log2 = log( A.size()-1 ) / log(2) + 1;
    int left = (1<<log2) - A.size();
    int idx = -1, offset = 0, root = idx;
    simulate_and_form(idx, (1<<log2), left, A, root, offset);
    answer(C, X, Y);
    return;
}

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