Submission #1029755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029755		boris_mihov	Robot Contest (IOI23_robot)	C++17	34 / 100	103 ms	6740 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 = 8;

struct State
{
    bool isDone;
    bool haventPassed;
    bool traversedThrough;
    bool isOutside;
    bool isOnStick;
    bool isCross;
    int dep;
 
    State()
    {
        isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick = 0;
    }
 
    int getNUM()
    {
        if (isDone) return 1;
        if (isOutside) return -2;
        if (isCross) return -1;
        if (haventPassed) return 0;
        if (isOnStick) return 8;
        return 3 * (int)(traversedThrough) + dep + 2; // zMAX == 7
    }
 
    void setState(int num)
    {
        isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick = 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;
        }

        if (num == 8)
        {
            isOnStick = 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)
        {
            return;
        }   

        if (state[0].isDone)
        {
            if (state[2].isOutside && state[3].isOutside)
            {
                set_instruction(nums, 1, 'T');
                return;
            }

            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (2 <= state[i].getNUM() && state[i].getNUM() <= 7)
                {
                    set_instruction(nums, 1, getDirection[i - 1]);
                    return;
                }
            }

            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (state[i].getNUM() == 8)
                {
                    set_instruction(nums, 1, getDirection[i - 1]);
                    return;
                }
            }
            
            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (state[i].getNUM() == 1)
                {
                    set_instruction(nums, 1, getDirection[i - 1]);
                    return;
                }
            }

            return;
        }

        char parDir = 'T';
        int cntDone = 0;
        for (int i = 1 ; i <= 4 ; ++i)
        {
            if (state[i].isDone)
            {
                parDir = getDirection[i - 1];
                cntDone++;
            }
        }

        if (cntDone && state[0].isOnStick)
        {
            set_instruction(nums, 1, 'H');
            return;
        }

        bool parentIsDiff = false;
        bool hasParent = false;
        if (2 <= state[0].getNUM() && state[0].getNUM() <= 7)
        {
            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (2 <= state[i].getNUM() && state[i].getNUM() <= 7)
                {
                    if (state[i].dep != (state[0].dep + 1) % 3)
                    {
                        hasParent = true;
                        // if (nums == std::vector <int> ({7, 6, 2, -1, -1}) && i == 1)
                        // {
                        //     exit(0);
                        // }

                        if (state[i].traversedThrough != state[0].traversedThrough)
                        {
                            parDir = getDirection[i - 1];
                            parentIsDiff = true;
                            if (state[i].traversedThrough)
                            {
                                break;   
                            }
                        }
                    }
                }
            }
        }

        // assert(nums != )

        if (cntDone || parentIsDiff)
        {
            if (!state[0].traversedThrough)
            {
                for (int i = 1 ; i <= 4 ; ++i)
                {
                    if (2 <= state[i].getNUM() && state[i].getNUM() <= 7 && (state[i].dep == (state[0].dep + 1) % 3) && !state[i].traversedThrough)
                    {
                        State newState = state[0];
                        newState.traversedThrough = 1;
                        set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
                        return;
                    }
                }
            }

            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (2 <= state[i].getNUM() && state[i].getNUM() <= 7  && (state[0].dep + 1) % 3 == state[i].dep)
                {
                    assert(state[0].traversedThrough || state[i].traversedThrough);
                    set_instruction(nums, state[0].getNUM(), getDirection[i - 1]);
                    return;
                }
            }

            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (2 <= state[i].getNUM() && state[i].getNUM() <= 7 && state[i].traversedThrough)
                {
                    // assert(state[0].traversedThrough || state[i].traversedThrough);
                    set_instruction(nums, 0, getDirection[i - 1]);
                    return;
                }
            }

            if (parDir == 'T')
            {
                return;
            }

            set_instruction(nums, 0, parDir);
            return;
        }

        int cntStick = 0;
        for (int i = 1 ; i <= 4 ; ++i)
        {
            if (state[i].isOnStick)
            {
                cntStick++;
            }
        }
 
        if (cntStick == 1 && !state[0].traversedThrough && ((state[1].isOutside && state[4].isOutside) || hasParent))
        {
            char parent = 'H';
            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (state[i].isCross || state[i].isOutside || state[i].traversedThrough || state[i].haventPassed || state[i].isOnStick)
                {
                    continue;
                }   
 
                if (state[i].dep != (state[0].dep + 1) % 3)
                {
                    parent = getDirection[i - 1];
                    break;
                }
            }
 
            if (parent == 'H' && !(state[1].isOutside && state[4].isOutside))
            {
                return;
            }

            set_instruction(nums, (parent == 'H' ? 1 : 8), 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};
            bool badNeighboor = false;
            for (int i = 1 ; i <= 4 ; ++i)
            {
                badNeighboor |= state[i].isOnStick;
                badNeighboor |= state[i].isDone;
                if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && !state[i].isOnStick && !state[i].isDone)
                {
                    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.isOnStick = 1;
                        }

                        // if (badNeighboor)
                        // {
                        //     newState = State();
                        //     newState.haventPassed = 1;
                        // }
 
                        set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
                        return;
                    }   
                }
 
                assert(false);
            } else
            {
                for (int i = 1 ; i <= 4 ; ++i)
                {
                    if (state[i].traversedThrough && !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.isOnStick = 1;
                        }
 
                        set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
                        return;
                    }   
                }

                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.isOnStick = 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].dep != (state[0].dep + 1) % 3)
                {
                    parent = getDirection[i - 1];
                }

                if (state[i].isDone || state[i].isOnStick)
                {
                    continue;
                }

                if (state[i].haventPassed)
                {
                    State newState = state[0];
                    set_instruction(nums, newState.getNUM(), getDirection[i - 1]);
                    return;
                }
 
                if (state[i].dep == (state[0].dep + 1) % 3)
                {
                    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;
        }

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

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

            if (state[i].isDone || state[i].isOnStick)
            {
                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:25:56: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   25 |         isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick = 0;
      |                                                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robot.cpp: In member function 'void State::setState(int)':
robot.cpp:40:56: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   40 |         isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick = 0;
      |                                                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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