Submission #597046

#	Time	Username	Problem	Language	Result	Execution time	Memory
597046		yutabi	Mechanical Doll (IOI18_doll)	C++14	100 / 100	89 ms	14092 KiB

doll

#include "doll.h"


#include <bits/stdc++.h>


#define pb push_back

#define INF 10000007


void create_circuit(int M, std::vector<int> A)
{
    A.pb(0);

    int N = A.size();

    std::vector <int> C(M+1,-1);

    std::vector <int> switches;
    std::vector <int> left, right;
    std::vector <int> X, Y;
    std::vector <int> level;
    std::vector <int> direct;

    std::vector <bool> bits;

    int a=N-1;

    while(a)
    {
        bits.pb(a%2);
        a/=2;
    }

    bits.pb(1);

    std::reverse(bits.begin(),bits.end());

    switches.pb(-1);
    left.pb(INF);
    right.pb(INF);
    X.pb(INF);
    Y.pb(INF);
    level.pb(0);
    direct.pb(0);


    for(int i=0,curr=0;i<N;)
    {
        if(direct[curr]==0)
        {
            direct[curr]=1;

            if(left[curr]==INF)
            {
                if(bits[level[curr]+1]==0)
                {
                    left[curr]=0;
                    X[curr]=-1;

                    bits[level[curr]+1]=1;

                    curr=0;
                }

                else if(level[curr]+2==bits.size())
                {
                    left[curr]=0;
                    X[curr]=A[i];

                    i++;

                    curr=0;
                }

                else
                {
                    left[curr]=switches.size();
                    X[curr]=-left[curr]-1;

                    switches.pb(X[curr]);
                    left.pb(INF);
                    right.pb(INF);
                    X.pb(INF);
                    Y.pb(INF);
                    level.pb(level[curr]+1);
                    direct.pb(0);

                    curr=left[curr];
                }
            }

            else
            {
                curr=left[curr];
            }
        }

        else
        {
            direct[curr]=0;

            if(right[curr]==INF)
            {
                if(bits[level[curr]+1]==0)
                {
                    right[curr]=0;
                    Y[curr]=-1;

                    bits[level[curr]+1]=1;

                    curr=0;
                }

                else if(level[curr]+2==bits.size())
                {
                    right[curr]=0;
                    Y[curr]=A[i];

                    i++;

                    curr=0;
                }

                else
                {
                    right[curr]=switches.size();
                    Y[curr]=-right[curr]-1;

                    switches.pb(Y[curr]);
                    left.pb(INF);
                    right.pb(INF);
                    X.pb(INF);
                    Y.pb(INF);
                    level.pb(level[curr]+1);
                    direct.pb(0);

                    curr=right[curr];
                }
            }

            else
            {
                curr=right[curr];
            }
        }
    }

    /*for(int i=0;i<C.size();i++)
    {
        printf("%d ",C[i]);
    }

    printf("\n");

    for(int i=0;i<level.size();i++)
    {
        printf("%d ",level[i]);
    }

    printf("\n");

    for(int i=0;i<left.size();i++)
    {
        printf("%d ",left[i]);
    }

    printf("\n");

    for(int i=0;i<right.size();i++)
    {
        printf("%d ",right[i]);
    }

    printf("\n");

    for(int i=0;i<X.size();i++)
    {
        printf("%d ",X[i]);
    }

    printf("\n");

    for(int i=0;i<Y.size();i++)
    {
        printf("%d ",Y[i]);
    }

    printf("\n");*/

    answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:67:38: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                 else if(level[curr]+2==bits.size())
doll.cpp:116:38: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |                 else if(level[curr]+2==bits.size())

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