Submission #847489

#	Time	Username	Problem	Language	Result	Execution time	Memory
847489		emeraldblock	Robot Contest (IOI23_robot)	C++17	100 / 100	101 ms	6268 KiB

robot

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

using namespace std;

enum Id {
    Bound = -2,
    Block,
    Empty,
    Path,
    West,
    South,
    East,
    North,
    Imp,
};
array<char,4> dirs{{'W','S','E','N'}};
pair<int,char> IMP = {Imp,'T'};

pair<int,char> move(array<int,5> S) {
    auto [h,w,s,e,n] = S;
    if (h == Empty) {
        if (w == Bound && n == Bound) {
            // start BFS phase
            if (s == Empty) {
                return {South,'S'};
            } else {
                return {East,'E'};
            }
        } else if (e == Bound && s == Bound) {
            // start pruning phase
            return {East,'H'};
        } else {
            // extend tree
            for (int i = 0; i < 4; ++i) {
                if (S[i+1]-West == (i+2)%4) return {West+i,dirs[i]};
            }
            return IMP;
        }
    } else if (0 <= h-West && h-West < 4) {
        int dir = h-West;
        if (S[dir+1]-West == (dir+2)%4) {
            // traverse tree
            int i = dir;
            do {
                i = (i+1)%4;
                if (S[i+1]-West == (i+2)%4 || S[i+1] == Empty) return {West+i,dirs[i]};
            } while (i != dir);
            return IMP;
        } else {
            // pruning phase
            int i = dir;
            bool path = false;
            do {
                i = (i+1)%4;
                // traverse to tile other than previous
                if (S[i+1]-West == (i+2)%4) return {h,dirs[i]};
                if (S[i+1] == Path) path = true;
            } while (i != dir);
            // prune
            return {
                path || (w == Bound && n == Bound) ? Path : Empty,
                e == Bound && s == Bound ? 'T' : dirs[i],
            };
        }
    } else {
        return IMP;
    }
}

#define FR(x) for (int x = Bound; x < Imp; ++x)

void program_pulibot()
{
    FR(h) FR(w) FR(s) FR(e) FR(n) {
        auto [Z,A] = move({h,w,s,e,n});
        set_instruction({h,w,s,e,n}, Z, A);
    }
}

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