Submission #1024864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024864		Svizel_pritula	Robot Contest (IOI23_robot)	C++17	85 / 100	146 ms	7416 KiB

robot

#include <bits/stdc++.h>

#include "robot.h"

using std::size_t;

const int unexplored = 0;
const int stroke = 1;
const int red_start = 2;
const int blue_start = 6;
const int unmark = 10;

inline int red(int parent) { return red_start - 1 + parent; }
inline int blue(int parent) { return blue_start - 1 + parent; }

inline bool is_red(int state) { return state >= red_start && state < red_start + 4; }
inline bool is_blue(int state) { return state >= blue_start && state < blue_start + 4; }
inline int parent(int state) { return (state - 2) % 4 + 1; }

inline int reverse(int dir)
{
    if (dir == 0)
        return 0;

    return (dir - 1 + 2) % 4 + 1;
}

const int max_color = 10;

const int min_color = 0;
const int min_state = -2;

const int obstacle = -1;
const int border = -2;

const std::array<char, 5> actions = {'H', 'W', 'S', 'E', 'N'};

#define FOR_STATE_VALUES(i) for (int i = min_state; i <= max_color; i++)

void set_instruction(std::array<int, 5> const &state, int color, char action)
{
    set_instruction(std::vector<int>(state.begin(), state.end()), color, action);
}

void program_state(int h, int w, int s, int e, int n)
{
    std::array<int, 5> state = {h, w, s, e, n};

    bool is_start = w == border && n == border;
    bool is_end = e == border && s == border;

    bool is_retracing = is_end;
    bool is_unmarking = false;

    for (int d = 1; d <= 4; d++)
    {
        if (state[d] == stroke)
            is_retracing = true;
        if (state[d] == unmark)
            is_unmarking = true;
    }

    if (is_unmarking)
    {
        for (int d = 1; d <= 4; d++)
            if ((is_red(state[d]) || is_blue(state[d])) && parent(state[d]) == reverse(d))
                return set_instruction(state, unmark, actions[d]);

        for (int d = 1; d <= 4; d++)
            if (state[d] == unmark)
                return set_instruction(state, unexplored, actions[d]);
    }

    if (h == unmark)
    {

        for (int d = 1; d <= 4; d++)
            if (is_blue(state[d]))
                return set_instruction(state, unmark, actions[d]);

        int red_count = 0;

        for (int d = 1; d <= 4; d++)
            if (is_red(state[d]))
                red_count++;

        if (red_count == 1 && !is_start)
            for (int d = 1; d <= 4; d++)
                if (is_red(state[d]))
                    return set_instruction(state, stroke, actions[d]);

        if (red_count == 0)
            return set_instruction(state, stroke, 'T');

        for (int d = 1; d <= 4; d++)
        {
            if (!is_red(state[d]))
                continue;

            for (int offset = 1; offset <= 3; offset++)
            {
                int prev = (d - 1 - offset + 4) % 4 + 1;

                if (is_red(state[prev]))
                    break;

                if (state[prev] == unexplored)
                    return set_instruction(state, unmark, actions[d]);
            }
        }
    }

    if (is_retracing)
    {
        if (is_red(h))
        {
            for (int offset = 1; offset <= 3; offset++)
            {
                int d = (parent(h) + offset - 1) % 4 + 1;

                if (is_red(state[d]) || is_blue(state[d]))
                    return set_instruction(state, unmark, actions[d]);
            }

            if (is_start)
                return set_instruction(state, stroke, 'T');

            return set_instruction(state, stroke, actions[parent(h)]);
        }

        if (h == unexplored)
            for (int d = 1; d <= 4; d++)
                if (is_red(state[d]))
                    return set_instruction(state, stroke, actions[d]);
    }

    if (is_start && h == unexplored)
        return set_instruction(state, red(1), 'H');

    if (h == unexplored)
    {
        for (int d = 1; d <= 4; d++)
            if (is_red(state[d]))
                return set_instruction(state, blue(d), actions[d]);
    }

    if (is_red(h))
    {
        for (int d = 1; d <= 4; d++)
            if (state[d] == unexplored || (is_red(state[d]) && parent(state[d]) == reverse(d)))
                return set_instruction(state, h, actions[d]);

        if (is_start)
            return set_instruction(state, blue(1), 'H');
        else
            return set_instruction(state, blue(parent(h)), actions[parent(h)]);
    }

    if (is_blue(h))
    {
        for (int d = 1; d <= 4; d++)
            if (is_blue(state[d]) && parent(state[d]) == reverse(d))
                return set_instruction(state, h, actions[d]);

        if (is_start)
            return set_instruction(state, red(1), 'H');
        else
            return set_instruction(state, red(parent(h)), actions[parent(h)]);
    }
}

void program_pulibot()
{
    FOR_STATE_VALUES(h)
    FOR_STATE_VALUES(w)
    FOR_STATE_VALUES(s)
    FOR_STATE_VALUES(e)
    FOR_STATE_VALUES(n)
    program_state(h, w, s, e, n);
}

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