Submission #1220350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220350		madamadam3	Robot Contest (IOI23_robot)	C++20	0 / 100	67 ms	5740 KiB

robot

#include "robot.h"
#include <bits/stdc++.h>

using namespace std;

/*
    boundary: state = -2
    obstacle: state = -1
    otherwise: state = colour

    n = up, s = down, w = left, e = right 

    S[0] is the state of cell (r, c).
    S[1] is the state of the cell to the west.
    S[2] is the state of the cell to the south.
    S[3] is the state of the cell to the east.
    S[4] is the state of the cell to the north.
*/

set<string> instr;

void instruction(vector<int> S, int Z, char A, bool ignore_duplicate = false) {
    string val = "";
    for (auto &el : S) val += to_string(el);

    if (instr.count(val) && !ignore_duplicate) {
        // cout << "Duplicate with: \n";
        // cout << val << "\n";
    } else {
        if (!instr.count(val)) set_instruction(S, Z, A);
        instr.insert(val);
    }
}

void solve_empty() {
    // if its entirely empty: go right while not a border on the right, then go up
    // if 

    instruction({0, -2, 0, 0, -2}, 1, 'E'); // at (0, 0): go right
    instruction({0, 1, 0, 0, -2}, 1, 'E'); // travelling along bottom: go right
    instruction({0, 1, 0, -2, -2}, 1, 'S'); // at (W, 0): go down
    instruction({0, 0, 0, -2, 1}, 1, 'S'); // travelling along side: go down
    instruction({0, 0, -2, -2, 1}, 1, 'T'); // at (W, H): terminate
}

void solve_h2() {
    // while possible, walk right
    // if not possible, go down/up
    // if at (W, H-1), go up

    // go right while possible
    for (auto &west_state : {-2, -1, 0, 1}) {
        for (auto &south_state : {-2, -1, 0, 1}) {
            for (auto &north_state : {-2, -1, 0, 1}) {
                instruction({0, west_state, south_state, 0, north_state}, 1, 'E');
            }
        }
    }

    // go down when needed
    for (auto &east_state : {-2, -1}) {
        for (auto &west_state : {-2, 1}) {
            instruction({0, west_state, 0, east_state, -2}, 1, 'S');
        }
    } 

    // go up when needed
    for (auto &east_state : {-1}) {
        for (auto &west_state : {-2, 1}) {
            instruction({0, west_state, -2, east_state, 0}, 1, 'N');
        }
    } 

    // at end
    for (auto &west_state : {-2, -1, 0, 1}) {
        for (auto &north_state : {-1, 0, 1}) {
            instruction({0, west_state, -2, -2, north_state}, 1, 'T');
        }
    }
}

const char DIR[5] = {'H', 'W', 'S', 'E', 'N'};
const int PERM[24][4] = {
    {1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {1, 4, 2, 3}, {1, 4, 3, 2}, 
    {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 3, 4, 1}, {2, 4, 1, 3}, {2, 4, 3, 1}, 
    {3, 1, 2, 4}, {3, 1, 4, 2}, {3, 2, 1, 4}, {3, 2, 4, 1}, {3, 4, 1, 2}, {3, 4, 2, 1}, 
    {4, 1, 2, 3}, {4, 1, 3, 2}, {4, 2, 1, 3}, {4, 2, 3, 1}, {4, 3, 1, 2}, {4, 3, 2, 1}
};

#define wall(x) for (auto &x : {-2, -1})
#define wall_or_empty(x) for (auto &x : {-2, -1, 0})
#define any(x) for (auto &x : {-2, -1, 0, 1, 2, 3, 4})
#define empty_blue(x) for (auto &x : {0, 1})
#define bygo(x) for (auto &x : {1, 2, 3, 4})
#define yg(x) for (auto &x : {1, 2})
#define ygo(x) for (auto &x : {2,3,4})

void solve_one_path() {
    // goal: simple cleaning routine (from root)

    // going from 0, 0
    instruction({0, -2, 0, 0, -2}, 2, 'E'); // can go right or down
    instruction({0, -2, -1, 0, -2}, 1, 'E'); // can go right only
    instruction({0, -2, 0, -1, -2}, 1, 'S'); // can go down only
    instruction({2, -2, 0, 0, -2}, 1, 'S'); // clearly we went right and it was bad
    instruction({2, -2, 0, 1, -2}, 1, 'T'); // we went right and it was good

    // unbranched fork: (1 blue, 1 wall, 2 empty)
    wall(a) {
        for (auto &perm : PERM) {
            vector<int> ins(5, 0);

            // case 1: we just arrived, and see the 2 options
            ins[perm[0]] = a; ins[perm[1]] = 1; ins[perm[2]] = 0; ins[perm[3]] = 0;
            instruction(ins, 2, DIR[perm[2]], true); // make green, go to first choice

            // case 2: we came back from our first choice, and it was bad, so we go to 2nd
            ins[0] = 2;
            instruction(ins, 1, DIR[perm[3]], true); // if green, go to 2nd choice, and path must be there

            // case 3: we came back from our second choice, and it was good, so we go to 2nd
            ins[perm[2]] = 1;
            instruction(ins, 1, 'T', true); // terminate because we've healed the green cell
        }
    }

    // branched fork (1 yellow/green/orange, 1 wall, 2 empty)
    wall(a) {ygo(b) {
        for (auto &perm : PERM) {
            vector<int> ins(5, 0);
            ins[perm[0]] = a; ins[perm[1]] = b; ins[perm[2]] = 0; ins[perm[3]] = 0; ins[0] = 0;

            // case 1: just arrived, go to first preference
            instruction(ins, 2, DIR[perm[2]]);

            // case 2: came back from first preference, it was good (is blue)
            ins[0] = 2; ins[perm[2]] = 1;
            instruction(ins, 1, DIR[perm[1]]);

            // case 3: came back from first preference, it was bad
            ins[perm[2]] = 0; ins[0] = 2;
            instruction(ins, 4, DIR[perm[3]]);

            // case 4: came back from 2nd preference, it was good
            ins[0] = 4; ins[perm[3]] = 1;
            instruction(ins, 1, DIR[perm[1]]);

            // case 5: came back from 2nd preference, it was bad
            ins[0] = 4; ins[perm[3]] = 0;
            instruction(ins, 0, DIR[perm[1]]);
        }
    }}

    // only one direction to travel in (2 walls, 1 blue/green/yellow/orange, and 1 empty)
    wall(a) {wall(b) {bygo(c) {
        for (auto &perm : PERM) {
            vector<int> ins(5, 0);
            
            ins[perm[0]] = a; ins[perm[1]] = b; ins[perm[2]] = c; ins[perm[3]] = 0; ins[0] = 0;
            instruction(ins, c == 1 ? 1 : 3, DIR[perm[3]], true);
        }   
    }}}

    // reversing a yellow (current is yellow, one is empty/blue, one is yellow/green/orange, 2 are walls)
    wall(a) {wall(b){ empty_blue(c) {
        for (auto &perm : PERM) {
            vector<int> ins(5, 0);
            ins[perm[0]] = a; ins[perm[1]] = b; ins[perm[2]] = 2; ins[perm[3]] = c; ins[0] = 3;
            instruction(ins, c, DIR[perm[2]], true);

            ins[perm[2]] = 3;
            instruction(ins, c, DIR[perm[2]], true);

            ins[perm[2]] = 4;
            instruction(ins, c, DIR[perm[2]], true);
        }   
    }}}
    
    // dead end reached (dead end = 3 wall 1 yellow/green/orange and cur is empty)
    wall(a) {wall(b) {wall(c) {ygo(d) {
        for (auto &perm : PERM) {
            vector<int> ins(5, 0);
            ins[perm[0]] = a; ins[perm[1]] = b; ins[perm[2]] = c; ins[perm[3]] = d;
            int colour = ins[2] == -2 && ins[3] == -2 ? 1 : 0;
            instruction(ins, colour, DIR[perm[3]], true);
        }
    }}}}

    // reached end
    instruction({0, 1, -2, -2, 0}, 1, 'T'); // reaced from blue path, we can stop
    instruction({0, 1, -2, -2, -1}, 1, 'T'); // same here ^
    instruction({0, 0, -2, -2, 1}, 1, 'T'); // reaced from blue path, we can stop
    instruction({0, -1, -2, -2, 1}, 1, 'T'); // same here ^

    instruction({0, 3, -2, -2, 0}, 1, 'W'); // reaced from yellow path, must turn around
    instruction({0, 3, -2, -2, -1}, 1, 'W'); // same here ^
    instruction({0, 0, -2, -2, 3}, 1, 'N'); // reaced from yellow path, must turn around
    instruction({0, -1, -2, -2, 3}, 1, 'N'); // same here ^

    instruction({0, 4, -2, -2, 0}, 1, 'W'); // reaced from orange path, must turn around
    instruction({0, 4, -2, -2, -1}, 1, 'W'); // same here ^
    instruction({0, 0, -2, -2, 4}, 1, 'N'); // reaced from orange path, must turn around
    instruction({0, -1, -2, -2, 4}, 1, 'N'); // same here ^
}

void program_pulibot() {
    // solve_empty();
    // solve_h2();
    solve_one_path();
}

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