oj.uz

Submission #597046

# Submission time Handle Problem Language Result Execution time Memory
597046 2022-07-15T12:23:30 Z yutabi Mechanical Doll (IOI18_doll) C++14
100 / 100
 89 ms 14092 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 34 ms 6076 KB Output is correct
3 Correct 31 ms 5668 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 46 ms 7620 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 34 ms 6076 KB Output is correct
3 Correct 31 ms 5668 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 46 ms 7620 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 64 ms 9968 KB Output is correct
9 Correct 59 ms 10180 KB Output is correct
10 Correct 87 ms 14092 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 34 ms 6076 KB Output is correct
3 Correct 31 ms 5668 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 46 ms 7620 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 64 ms 9968 KB Output is correct
9 Correct 59 ms 10180 KB Output is correct
10 Correct 87 ms 14092 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 87 ms 13664 KB Output is correct
15 Correct 58 ms 9652 KB Output is correct
16 Correct 82 ms 13216 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 84 ms 13852 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 51 ms 9472 KB Output is correct
3 Correct 55 ms 9472 KB Output is correct
4 Correct 80 ms 12824 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 51 ms 9472 KB Output is correct
3 Correct 55 ms 9472 KB Output is correct
4 Correct 80 ms 12824 KB Output is correct
5 Correct 80 ms 13212 KB Output is correct
6 Correct 83 ms 12964 KB Output is correct
7 Correct 79 ms 12988 KB Output is correct
8 Correct 81 ms 12956 KB Output is correct
9 Correct 53 ms 9436 KB Output is correct
10 Correct 79 ms 12872 KB Output is correct
11 Correct 89 ms 12860 KB Output is correct
12 Correct 51 ms 9388 KB Output is correct
13 Correct 53 ms 9484 KB Output is correct
14 Correct 61 ms 9508 KB Output is correct
15 Correct 64 ms 9456 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 49 ms 9284 KB Output is correct
18 Correct 54 ms 9376 KB Output is correct
19 Correct 56 ms 9380 KB Output is correct
20 Correct 79 ms 12908 KB Output is correct
21 Correct 81 ms 12896 KB Output is correct
22 Correct 80 ms 12848 KB Output is correct