Submission #1220412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220412		madamadam3	Robot Contest (IOI23_robot)	C++20	18 / 100	67 ms	5960 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 : {-1, 0})
#define any(x) for (auto &x : {-2, -1, 0, 1, 2, 3, 4, 5})
#define empty_blue(x) for (auto &x : {0, 1})
#define bygo(x) for (auto &x : {1, 2, 3, 4, 5})
#define yg(x) for (auto &x : {1, 2})
#define ygo(x) for (auto &x : {2,3,4, 5})

void rotate(vector<int> S, int Z, int C) {
    set<string> seen;

    for (auto &perm : PERM) {
        vector<int> ins(5);
        ins[0] = S[0];
        ins[perm[0]] = S[1];
        ins[perm[1]] = S[2];
        ins[perm[2]] = S[3];
        ins[perm[3]] = S[4];

        char dir;
        if (C == 0) dir = 'T';
        else if (C == 5) dir = 'H';
        else dir = DIR[perm[C-1]];

        string v = ""; for (auto &el : ins) v+=to_string(el);
        if (seen.count(v)) continue;
        seen.insert(v);
        instruction(ins, Z, dir);
    }
}

void corners() {
    // (1) special cases for the corners
    // (a) 0, 0
    instruction({0, -2, -1, 0, -2}, 1, 'E'); // only right
    instruction({0, -2, 0, -1, -2}, 1, 'S'); // only down

    instruction({0, -2, 0, 0, -2}, 2, 'E'); // both options, go right
    instruction({2, -2, 0, 0, -2}, 1, 'S'); // option 1 bad, go down
    instruction({2, -2, 0, 1, -2}, 1, 'T'); // option 1 good, make blue and terminate
    instruction({2, -2, 1, 0, -2}, 1, 'T'); // option 2 good, make blue and terminate

    // (b) (W, 0) or (0, W)
    bygo(col) {
        // keep the colour, going down or right
        instruction({0, col, 0, -2, -2}, col, DIR[2]);
        instruction({0, 0, col, -2, -2}, col, DIR[1]);

        instruction({0, -2, -2, col, 0}, col, DIR[4]);
        instruction({0, -2, -2, 0, col}, col, DIR[3]);

        // reverse a yellow
        if (col == 1) continue;
        // go in opposite direction if we have a blue
        instruction({3, col, 1, -2, -2}, 1, DIR[1]);
        instruction({3, 1, col, -2, -2}, 1, DIR[2]);

        instruction({3, -2, -2, col, 1}, 1, DIR[3]);
        instruction({3, -2, -2, 1, col}, 1, DIR[4]);

        wall_or_empty(a) {
            instruction({0, col, a, -2, -2}, 0, DIR[1]);
            instruction({0, a, col, -2, -2}, 0, DIR[2]);
            instruction({3, col, a, -2, -2}, 0, DIR[1]);
            instruction({3, a, col, -2, -2}, 0, DIR[2]);

            instruction({0, -2, -2, col, a}, 0, DIR[3]);
            instruction({0, -2, -2, a, col}, 0, DIR[4]);
            instruction({3, -2, -2, col, a}, 0, DIR[3]);
            instruction({3, -2, -2, a, col}, 0, DIR[4]);
        }
    }

    // (c) (W, H)
    wall_or_empty(c) { // we can end
        instruction({0, c, -2, -2, 1}, 1, 'T');
        instruction({0, 1, -2, -2, c}, 1, 'T');

        ygo(c2) { // need to go back
            instruction({0, c, -2, -2, c2}, 1, DIR[4]);
            instruction({0, c2, -2, -2, c}, 1, DIR[1]);
        }
    }
}

void forced_movements() {
    // (2) we are carrying the previous colour with us to the only empty square we have
    wall(a) {
        rotate({0, a, -1, 0, 1}, 1, 3);
        ygo(b) rotate({0, a, -1, 0, b}, 3, 3);
    }
}

void clean_to_green() { // or orange
    // (3) undoing a forward movement with yellow colour to clean it
    wall(a) ygo(b) rotate({3, a, -1, b, 0}, 0, 3); // case 1: cleaning the yellow colour
    wall(a) ygo(b) rotate({3, a, -1, b, 1}, 1, 3); // case 2: found the answer we're setting everything blue until we reach green/orange
}

void dead_ends() {
    // (4) we hit a dead end in our search down a branch
    wall(a) {
        ygo(b) rotate({0, a, -1, -1, b}, 0, 4);
    }
}

void blue2branch() {
    // (5) our parent is blue, but we have 2 children
   
    wall(a) rotate({0, a, 1, 0, 0}, 2, 4); // case 1: we just arrived, so set to green and go down child 1
    wall(a) rotate({2, a, 1, 1, 0}, 1, 0); // case 2: we've come back from child 1 and child 1 is blue (we found the shortest path)
    wall(a) rotate({2, a, 1, 0, 0}, 1, 3); // case 3: come back from child 1, and it doesnt lead to the answer
}

void blue3branch() {
    // (6) our parent is blue, but we have 3 children

    rotate({0, 1, 0, 0, 0}, 2, 4); // case 1: just arrived, go down first preference
    rotate({2, 1, 1, 0, 0}, 1, 0); // case 2: first preference good, set to blue and terminate
    rotate({2, 1, 0, 0, 0}, 4, 3); // case 3: first path was bad, going down second path
    rotate({4, 1, 1, 0, 0}, 1, 0); // case 4: second path good, terminating
    rotate({4, 1, 0, 0, 0}, 1, 2); // case 5: second path bad, going down third path
}

void yellow2branch() {
    // (7) our parent is yellow/orange/green, but we have 2 children

    ygo(p) {
        wall(a) rotate({0, a, p, 0, 0}, 2, 4); // case 1: we just arrived, so set to green and go down child 1
        wall(a) rotate({2, a, p, 1, 0}, 1, 2); // case 2: we've come back from child 1 and child 1 is blue (we found the shortest path)
        wall(a) rotate({2, a, p, 0, 0}, 4, 3); // case 3: come back from child 1, and it doesnt lead to the answer, so set to orange and go down 2
        wall(a) rotate({4, a, p, 1, 0}, 1, 2); // case 4: come back from child 2, and it is the answer
        wall(a) rotate({4, a, p, 0, 0}, 0, 2); // case 5: come back from child 2, and it isnt the answer
    }
}

void yellow3branch() {
    // (8) our parent is yellow/green/orange, but we have 3 children
    ygo(p) {
        rotate({0, p, 0, 0, 0}, 2, 4); // case 1: just arrived, go down first preference
        rotate({2, p, 1, 0, 0}, 1, 1); // case 2: first preference good, set to blue and go to parent
        rotate({2, p, 0, 0, 0}, 4, 3); // case 3: first path was bad, going down second path
        rotate({4, p, 1, 0, 0}, 1, 1); // case 4: second path good, terminating
        rotate({4, p, 0, 0, 0}, 5, 2); // case 5: second path bad, going down third path
        rotate({5, p, 1, 0, 0}, 1, 1); // case 6: third path good: set to blue and go to parent
        rotate({5, p, 0, 0, 0}, 0, 1); // case 7: third path bad: set to empty and go to parent
    }
}

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

    corners();
    forced_movements();
    clean_to_green();
    dead_ends();
    blue2branch();
    blue3branch();
    yellow2branch();
    yellow3branch();
}

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

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