Submission #1240247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240247		Adriano	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	168 ms	13184 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.resize(M+1); // Just to make it explicit
    C[0] = A[0];

    A.push_back(0);
    for ( int _ = 0; _ < A.size()-1; ++_ )
    {
        directed_adj[ A[_] ].push_back( A[_+1] ); // Directed Graph formation
    }

    for ( int i = 1; i <= M; ++i )
    {
        if ( directed_adj[i].empty() )
            continue;
        else if ( directed_adj[i].size() == 1)
        {
            C[i] = directed_adj[i][0];
            continue;
        }
        int log2 = log( directed_adj[i].size()-1 ) / log(2) + 1;
        int left = (1<<log2) - directed_adj[i].size();
        cerr << left << '\n';
        int idx = -s_count - 1, offset = 0;
        int root = idx;
        C[i] = idx;
        simulate_and_form(idx, (1<<log2), left, directed_adj[i], 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: 41.553 / 56