Submission #1241781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241781		Adriano	Mechanical Doll (IOI18_doll)	C++17	0 / 100	0 ms	328 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);

    size_t N = A.size();
    printf("%d N:X %llu d %llu\n", (int)(N+log(N)/log(2)), X.size(), X.size()*100/(int)(N+log(N)/log(2)));
    puts( (X.size() <= N + log(N)/log(2)? "YES" : "NO"));
    answer(C, X, Y);
    return;
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:92:23: warning: format '%llu' expects argument of type 'long long unsigned int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   92 |     printf("%d N:X %llu d %llu\n", (int)(N+log(N)/log(2)), X.size(), X.size()*100/(int)(N+log(N)/log(2)));
      |                    ~~~^                                    ~~~~~~~~
      |                       |                                          |
      |                       long long unsigned int                     std::vector<int>::size_type {aka long unsigned int}
      |                    %lu
doll.cpp:92:30: warning: format '%llu' expects argument of type 'long long unsigned int', but argument 4 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   92 |     printf("%d N:X %llu d %llu\n", (int)(N+log(N)/log(2)), X.size(), X.size()*100/(int)(N+log(N)/log(2)));
      |                           ~~~^                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                              |                                                   |
      |                              long long unsigned int                              std::vector<int>::size_type {aka long unsigned int}
      |                           %lu

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