Submission #1220962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220962		madamadam3	Robot Contest (IOI23_robot)	C++20	26 / 100	77 ms	5972 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, 4})
#define wempty(x) for (auto &x : {-1, 0})
#define EBX(x) for (auto &x : {0, -1, -2, 4})
#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})
#define RE(x) for (auto &x : {0, 4})
#define rwall(x) for (auto &x : {-1, -2, 4})
#define ewall(x) for (auto &x : {-1, -2, 0})

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 rotate_half(vector<int> S, int Z, int C) {
    set<string> seen;

    for (auto &perm : PERM) {
        if ((perm[2] != 3 && perm[2] != 4) || (perm[3] != 3 && perm[3] != 4)) continue;
        
        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 lattice_dead() {
//     // dead end in a lattice means south and east are both walls
    
//     wall(a) rotate_half({})
// }

void solve_lattice() {
    // predicated on knowing that if we find the end, and we only went right or down, we got a shortest path
    // every cell is a potential branchpoint

    /*
        in essence: 
        (1) if cell empty, set to yellow and go right.
        (2) if cell yellow, 
            (a) if right is blue, keep bringing the blue to the start
            (b) if right is empty, set to green and go down
        (3) if cell green,
            (a) if down is blue, keep bringing blue to the start
            (b) if down is empty, set to empty and go to parent
    */

    // at start nicely
    wall_or_empty(south) instruction({3, -2, south, 1, -2}, 1, 'H');
    wall_or_empty(east) instruction({2, -2, 1, east, -2}, 1, 'H');

    // dead ends
    any(west) rwall(east) rwall(south) if (!(east == south && east == -2)) instruction({0, west, south, east, 2}, 4, 'N');
    any(north) rwall(east) rwall(south) if (!(east == south && east == -2)) instruction({0, 3, south, east, north}, 4, 'W');

    // at (W,H)
    any(west) instruction({0, west, -2, -2, 2}, 1, 'N');
    any(north) instruction({0, 3, -2, -2, north}, 1, 'W');

    // empty cell(s)
    any(west) any(north) RE(c) instruction({0, west, 0, c, north}, 2, 'S');
    any(west) any(north) RE(c) instruction({0, west, 4, 0, north}, 3, 'E');
    any(west) any(north) RE(c) instruction({2, west, c, 0, north}, 3, 'E'); // go down

    any(west) EBX(c) instruction({2, west, 1, c, 2}, 1, 'H');
    any(west) EBX(c) instruction({3, west, c, 1, 2}, 1, 'H'); // bring the blue north
    any(west) ewall(c) instruction({1, west, 1, c, 2}, 1, 'N');
    any(west) ewall(c) instruction({1, west, c, 1, 2}, 1, 'N'); // bring the blue north

    any(west) instruction({3, west, 4, 4, 2}, 4, 'N'); // bring the empty north

    any(north) EBX(c) instruction({2, 3, 1, c, north}, 1, 'H');
    any(north) EBX(c) instruction({3, 3, c, 1, north}, 1, 'H'); // bring the blue west
    any(north) ewall(c) instruction({1, 3, 1, c, north}, 1, 'W');
    any(north) ewall(c) instruction({1, 3, c, 1, north}, 1, 'W'); // bring the blue west

    any(north) instruction({3, 3, 4, 4, north}, 4, 'W'); // bring the empty west

    // walls
    any(west) any(north) wall(east) instruction({0, west, 0, east, north}, 2, 'S');
    any(west) any(north) wall(south) instruction({0, west, south, 0, north}, 3, 'E');

    any(west) wall(east) instruction({2, west, 4, east, 2}, 4, 'N');
    any(north) wall(east) instruction({2, 3, 4, east, north}, 4, 'W');

    any(west) wall(south) instruction({3, west, south, 4, 2}, 4, 'N');
    any(north) wall(south) instruction({3, 3, south, 4, north}, 4, 'W');

    // cleanup
    wempty(south) instruction({1, -2, south, 1, -2}, 1, 'T'); // final terminate
    wempty(east) instruction({1, -2, 1, east, -2}, 1, 'T');

    any(west) ewall(east) ewall(south) if (!(east == south && east == -2)) instruction({4, west, south, east, 4}, 0, 'N');
    any(north) ewall(east) ewall(south) if (!(east == south && east == -2) && !(north == 1)) instruction({4, 4, south, east, north}, 0, 'W');

    // go down from blue
    any(west) any(north) instruction({1, west, 4, 1, north}, 1, 'S'); // east is blue: go down
    any(west) any(north) instruction({1, west, 1, 4, north}, 1, 'E'); // south is blue: go east

    // go up to blue
    ewall(south) ewall(east) any(north) instruction({4, 1, south, east, north}, 0, 'W'); // west is blue: go left
    ewall(south) ewall(east) any(west) instruction({4, west, south, east, 1}, 0, 'N'); // north is blue: go up

    // go down/right from red
    any(north) any(west) instruction({4, west, 4, 4, north}, 4, 'S');
    any(north) any(west) ewall(east) instruction({4, west, 4, east, north}, 4, 'S');
    any(north) any(west) ewall(south) instruction({4, west, south, 4, north}, 4, 'E');
}

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

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