Submission #1031258

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

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

        if (num == 9)
        {
            isOnStick2 = 1;
            return;
        }

        if (num == 10)
        {
            isOnStick3 = 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;
        }   

        int cnt1 = 0;
        int cnt8 = 0;
        int cnt9 = 0;
        int cnt10 = 0;

        for (int i = 1 ; i <= 4 ; ++i)
        {
            if (state[i].getNUM() == 1) cnt1++;
            if (state[i].getNUM() == 8) cnt8++;
            if (state[i].getNUM() == 9) cnt9++;
            if (state[i].getNUM() == 10) cnt10++;
        }

        if (state[0].getNUM() == 9 && cnt1)
        {
            if (state[2].isOutside && state[3].isOutside)
            {
                set_instruction(nums, 1, 'T');
            } else
            {
                set_instruction(nums, 1, 'H');
            }

            return;
        }

        if (state[0].getNUM() == 1 && cnt9)
        {
            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() == 9)
                {
                    set_instruction(nums, 1, getDirection[i - 1]);
                    return;
                }
            }
            
            return;
        }

        if (state[0].getNUM() == 10 && cnt8)
        {
            if (state[2].isOutside && state[3].isOutside)
            {
                char parent = 'H';
                for (int i = 1 ; i <= 4 ; ++i)
                {
                    if (state[i].getNUM() == 8)
                    {
                        parent = getDirection[i - 1];
                    }
                }

                set_instruction(nums, 9, parent);
                return;
            }

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

        if (state[0].getNUM() == 8 && cnt9)
        {
            if (state[1].isOutside && state[4].isOutside)
            {
                set_instruction(nums, 1, 'H');
                return;
            }

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

        bool hasParent = false;
        bool parentIsDiff = 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 (state[i].traversedThrough != state[0].traversedThrough)
                        {
                            parentIsDiff = true;
                            if (!state[i].traversedThrough)
                            {
                                break;
                            }
                        }
                    }
                }
            }
        }           

        if (cnt1 || 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)
                {
                    set_instruction(nums, state[0].getNUM(), getDirection[i - 1]);
                    return;
                }
            }

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

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

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

            // for (int i = 1 ; i <= 4 ; ++i)
            // {
            //     if (state[i].isDone || (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && state[i].traversedThrough != state[0].traversedThrough && state[i].dep != (state[0].dep + 1) % 3))
            //     { 
                    
            //         set_instruction(nums, 0, getDirection[i - 1]);
            //         return;
            //     }   
            // }

            return;
        }

        if (cnt10 && 2 <= state[0].getNUM() && state[0].getNUM() <= 7)
        {
            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].isOnStick3)
                {
                    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;
            }

            if (parent != 'H')
            {
                set_instruction(nums, 10, parent);
                return;
            }

            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (state[i].getNUM() == 10)
                {
                    parent = getDirection[i - 1];
                }
            }

            set_instruction(nums, 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;
            }

            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (state[i].traversedThrough)
                {
                    set_instruction(nums, 0, getDirection[i - 1]);
                    return;
                }   
            }
 
            bool is[3] = {0, 0, 0};
            for (int i = 1 ; i <= 4 ; ++i)
            {
                if (!state[i].haventPassed && !state[i].isCross && !state[i].isOutside && !state[i].isOnStick1 && !state[i].isOnStick2 && !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.isOnStick3 = 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.isOnStick3 = 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.isOnStick3 = 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].isOnStick1 || state[i].isOnStick2 || state[i].isOnStick3)
                {
                    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].isOnStick1 || state[i].isOnStick2 || state[i].isOnStick3)
            {
                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:27:56: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |         isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick1 = isOnStick2 = isOnStick3 = 0;
      |                                                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robot.cpp: In member function 'void State::setState(int)':
robot.cpp:44:56: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   44 |         isDone = traversedThrough = haventPassed = dep = isOutside = isCross = isOnStick1 = isOnStick2 = isOnStick3 = 0;
      |                                                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robot.cpp: In function 'void rec(int)':
robot.cpp:213:14: warning: variable 'hasParent' set but not used [-Wunused-but-set-variable]
  213 |         bool hasParent = false;
      |              ^~~~~~~~~

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