Submission #1029370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029370		boris_mihov	Robot Contest (IOI23_robot)	C++17	59 / 100	120 ms	6476 KiB

robot

#include "robot.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 20;
const int Z_MAX = 7;

struct State
{
    bool isDone;
    bool haventPassed;
    bool traversedThrough;
    bool isOutside;
    bool isCross;
    int dep;

    State()
    {
        isDone = traversedThrough = haventPassed = dep = isOutside = isCross = 0;
    }

    int getNUM()
    {
        if (isDone) return 1;
        if (isOutside) return -2;
        if (isCross) return -1;
        if (haventPassed) return 0;
        return 3 * (int)(traversedThrough) + dep + 2; // zMAX == 7
    }

    void setState(int num)
    {
        isDone = traversedThrough = haventPassed = dep = isOutside = isCross = 0;
        if (num == -2)
        {
            isOutside = 1;
            return;
        }

        if (num == -1)
        {
            isCross = 1;
            return;
        }

        if (num == 0)
        {
            haventPassed = 1;
            return;
        }

        if (num == 1)
        {
            isDone = 1;
            return;
        }
        
        assert(num <= 7);
        if (num > 4)
        {
            traversedThrough = 1;
            dep = num - 5;
            return;
        }

        dep = num - 2;
    }
};

State state[5];
std::vector <int> nums;

bool isNeighboor[5];
char getDirection[4] = {'W', 'S', 'E', 'N'};
char getOpposite[4] = {'E', 'N', 'W', 'S'};

void rec(int idx)
{
    if (idx == 5)
    {
        if (state[0].isCross || state[0].isOutside || state[0].isDone)
        {
            return;
        }   

        bool amIdone = false;
        for (int i = 1 ; i <= 4 ; ++i)
        {
            if (state[i].isDone)
            {
                amIdone = true;
                break;
            }
        }

        if (amIdone)
        {
            char parent = 'T';
            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (state[i].isCross || state[i].isOutside || state[i].traversedThrough || state[i].haventPassed || state[i].isDone)
                {
                    continue;
                }   

                if (state[i].dep != (state[0].dep + 1) % 3)
                {
                    parent = getDirection[i - 1];
                    break;
                }
            }

            if (parent == 'T' && !(state[1].isOutside && state[4].isOutside))
            {
                return;
            }

            State newState = state[0];
            newState.isDone = 1;
            set_instruction(nums, newState.getNUM(), parent);
            return;
        }

        if (state[0].haventPassed)
        {
            if (state[1].isOutside && state[4].isOutside)
            {
                State newState = state[0];
                newState.haventPassed = 0;
                newState.dep = 0;
                set_instruction(nums, newState.getNUM(), 'H');
                return;
            }

            bool is[3] = {0, 0, 0};
            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside)
                {
                    is[state[i].dep] = 1;
                }   
            }

            int cntAre = 0;
            cntAre += is[0];
            cntAre += is[1];
            cntAre += is[2];

            if (cntAre == 0 || cntAre == 3)
            {
                return;
            }

            int parDep = -1;
            int myDep = -1;
            if (cntAre == 1)
            {   
                if (is[0])
                {
                    parDep = 0;
                    myDep = 1;
                } else if (is[1])
                {
                    parDep = 1;
                    myDep = 2;
                } else
                {
                    parDep = 2;
                    myDep = 0;
                }
            } else
            {
                if (is[0] && is[1])
                {
                    parDep = 0;
                    myDep = 1;
                } else if (is[0] && is[2])
                {
                    parDep = 2;
                    myDep = 0;
                } else if (is[1] && is[2])
                {
                    parDep = 1;
                    myDep = 2;
                }
            }

            int countCandidates = 0;
            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].dep == parDep)
                {
                    countCandidates++;
                }   
            }

            assert(countCandidates);
            if (countCandidates == 1)
            {
                for (int i = 1 ; i <= 4 ; ++i)
                {
                    if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].dep == parDep)
                    {
                        State newState;
                        newState.traversedThrough = 1;
                        newState.dep = myDep;

                        if (state[2].isOutside && state[3].isOutside)
                        {
                            newState.isDone = 1;
                        }

                        set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
                        return;
                    }   
                }

                assert(false);
            } else
            {
                for (int i = 1 ; i <= 4 ; ++i)
                {
                    if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].dep == parDep && state[i].traversedThrough)
                    {
                        State newState;
                        newState.traversedThrough = 1;
                        newState.dep = myDep;
                        
                        if (state[2].isOutside && state[3].isOutside)
                        {
                            newState.isDone = 1;
                        }

                        set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
                        return;
                    }   
                }

                return;
                assert(false);
            }
        }

        if (!state[0].traversedThrough)
        {
            char parent = 'H';
            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (state[i].isCross || state[i].isOutside || state[i].traversedThrough)
                {
                    continue;
                }

                if (state[i].haventPassed)
                {
                    State newState = state[0];
                    if (!(state[1].isOutside && state[4].isOutside))
                    {
                        newState.traversedThrough = 1;
                    }

                    set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
                    return;
                }

                if (state[i].dep != (state[0].dep + 1) % 3)
                {
                    parent = getDirection[i - 1];
                } else
                {
                    set_instruction(nums, state[0].getNUM(), getDirection[i - 1]);
                    return;
                }
            }

            if (parent == 'H' && !(state[1].isOutside && state[4].isOutside))
            {
                return;
            }

            State newState = state[0];
            newState.traversedThrough = 1;
            set_instruction(nums, newState.getNUM(), parent);
            return;
        }

        if (!(state[1].isOutside && state[4].isOutside))
        {
            bool isParentTraversed = false;
            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (state[i].isCross || state[i].isOutside || state[i].haventPassed)
                {
                    continue;
                }   

                if (state[i].dep != (state[0].dep + 1) % 3)
                {
                    isParentTraversed = state[i].traversedThrough;
                    break;
                }
            }

            if (!isParentTraversed)
            {
                State newState = state[0];
                newState.traversedThrough = 0;
                set_instruction(nums, newState.getNUM(), 'H');
                return;
            }
        }

        char parent = 'H';
        for (int i = 1 ; i <= 4 ; ++i)
        {
            if (state[i].isCross || state[i].isOutside || !state[i].traversedThrough)
            {
                continue;
            }

            if (state[i].haventPassed)
            {
                return;
            }

            if (state[i].dep != (state[0].dep + 1) % 3)
            {
                parent = getDirection[i - 1];
            } else
            {
                set_instruction(nums, state[0].getNUM(), getDirection[i - 1]);
                return;
            }
        }

        if (parent == 'H' && !(state[1].isOutside && state[4].isOutside))
        {
            return;
        }

        State newState = state[0];
        newState.traversedThrough = 0;
        set_instruction(nums, newState.getNUM(), parent);
        return;
    }

    for (int curr = -2 ; curr <= Z_MAX ; ++curr)
    {
        state[idx].setState(curr);
        nums[idx] = curr;
        rec(idx + 1);
    }
}

void program_pulibot()
{
    nums.resize(5);
    rec(0);
}

Compilation message (stderr)

robot.cpp: In constructor 'State::State()':
robot.cpp:24:56: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   24 |         isDone = traversedThrough = haventPassed = dep = isOutside = isCross = 0;
      |                                                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
robot.cpp: In member function 'void State::setState(int)':
robot.cpp:38:56: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   38 |         isDone = traversedThrough = haventPassed = dep = isOutside = isCross = 0;
      |                                                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 3 / 6
• Subtask 2: 5 / 10
• Subtask 3: 9 / 18
• Subtask 4: 10 / 20
• Subtask 5: 31.9999999994 / 46