Submission #1058364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058364		perekopskad	Robot Contest (IOI23_robot)	C++17	16 / 100	81 ms	5716 KiB

robot

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define el '\n'
#define ff first
#define ss second
#define pii pair <ll, ll>
#define pb push_back
#define mkp make_pair
#define fr(i, l, r) for(ll i = l; i <= r; i++)
#define debug(x) \
    { cout << #x << " = " << x << el; }

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

const ll N = 1e3 + 10;
const ll M = 1e5 + 10;
const ll K = 400;
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll LOG = 20;
const ll mod = 1000002022;
mt19937 rnd(time(0));

/*
9 9
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0

15 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
*/

void set_instruction(std::vector<int> S, int Z, char A);

void program_pulibot() {
    for(int i1 = 0; i1 <= 2; i1++) {
        for(int i2 = -2; i2 <= 1; i2++) {
            for(int i3 = -2; i3 <= 3; i3++) {
                for(int i4 = -2; i4 <= 3; i4++) {
                    for(int i5 = -2; i5 <= 2; i5++) {
                        if(i1 == 0) {
                            if(i4 == 0)
                                set_instruction({i1, i2, i3, i4, i5}, 1, 'E');
                            else if(i3 == 0)
                                set_instruction({i1, i2, i3, i4, i5}, 1, 'S');
                            else if(i3 == -2 && i4 == -2) {
                                if(i2 == 1) set_instruction({i1, i2, i3, i4, i5}, 1, 'W');
                                else if(i5 == 1 || i5 == 2) set_instruction({i1, i2, i3, i4, i5}, 1, 'N');
                            }
                            else {
                                if(i2 == 1)
                                    set_instruction({i1, i2, i3, i4, i5}, 3, 'W');
                                else if(i5 == 1 || i5 == 2)
                                    set_instruction({i1, i2, i3, i4, i5}, 3, 'N');
                            }
                        }
                        if(i1 == 1) {
                            if(i4 == 3 && i3 == 0)
                                set_instruction({i1, i2, i3, i4, i5}, 2, 'S');
                            else if(i3 == 1) {
                                if(i2 == 1) set_instruction({i1, i2, i3, i4, i5}, 1, 'W');
                                else if(i5 == 1 || i5 == 2) set_instruction({i1, i2, i3, i4, i5}, 1, 'N');
                                else if(i2 == -2 && i5 == -2) set_instruction({i1, i2, i3, i4, i5}, 1, 'T');
                            }
                            else if(i4 == 1) {
                                if(i2 == 1) set_instruction({i1, i2, i3, i4, i5}, 1, 'W');
                                else if(i5 == 1 || i5 == 2) set_instruction({i1, i2, i3, i4, i5}, 1, 'N');
                                else if(i2 == -2 && i5 == -2) set_instruction({i1, i2, i3, i4, i5}, 1, 'T');
                            }
                            else if(i2 == 1) set_instruction({i1, i2, i3, i4, i5}, 3, 'W');
                            else if(i5 == 1 || i5 == 2) set_instruction({i1, i2, i3, i4, i5}, 3, 'N');
                        }
                        if(i1 == 2) {
                            if(i3 == 1) {
                                if(i2 == 1) set_instruction({i1, i2, i3, i4, i5}, 1, 'W');
                                else if(i5 == 1 || i5 == 2) set_instruction({i1, i2, i3, i4, i5}, 1, 'N');
                                else if(i2 == -2 && i5 == -2) set_instruction({i1, i2, i3, i4, i5}, 1, 'T');
                            }
                            else if(i4 == 1) {
                                if(i2 == 1) set_instruction({i1, i2, i3, i4, i5}, 1, 'W');
                                else if(i5 == 1 || i5 == 2) set_instruction({i1, i2, i3, i4, i5}, 1, 'N');
                                else if(i2 == -2 && i5 == -2) set_instruction({i1, i2, i3, i4, i5}, 1, 'T');
                            }
                            else if(i2 == 1) set_instruction({i1, i2, i3, i4, i5}, 3, 'W');
                            else if(i5 == 1 || i5 == 2) set_instruction({i1, i2, i3, i4, i5}, 3, 'N');
                        }
                    }
                }
            }
        }
    }
}

/*
static const int MAX_COLOR = 19;
static const int MAX_STATE = 5153632; // = (MAX_COLOR + 3) ^ 5
static const int MAX_STEPS = 500000;

static std::ofstream output;

[[noreturn]] static void die(const std::string &message)
{
    std::cout << message << "\n";
    output.close();
    exit(0);
}

[[noreturn]] static void pv(const std::string &message)
{
    die("Protocol Violation: " + message);
}

static int encode_state(const std::vector<int> &S)
{
    int state = 0;
    for (int s : S)
    {
        state = (MAX_COLOR + 3) * state + s + 2;
    }
    return state;
}

struct instruction
{
    char color;
    char action;
};

static int encode_instr(instruction instr)
{
    if (!instr.action)
    {
        return 0;
    }
    int index = std::string("HWSENT").find_first_of(instr.action) + 1;
    return (index << 5) | instr.color;
}

static instruction program[MAX_STATE];

void set_instruction(std::vector<int> S, int Z, char A)
{

    if (S.size() != 5)
    {
        pv("Invalid array");
    }
    for (int s : S)
    {
        if (s < -2 || s > MAX_COLOR)
        {
            pv("Invalid array");
        }
    }
    if (Z < 0 || Z > MAX_COLOR)
    {
        pv("Invalid color");
    }
    if (std::string("HWSENT").find_first_of(A) == std::string::npos)
    {
        pv("Invalid action");
    }
    int code = encode_state(S);
    if (program[code].action)
    {
        pv("Same state array");
    }
    program[code].color = Z;
    program[code].action = A;
}

static std::vector<std::vector<int>> cells;
static int H, W;
static int rx = 1, ry = 1;

static bool step(instruction instr)
{
    cells[rx][ry] = instr.color;
    switch (instr.action)
    {
    case 'H':
        break;
    case 'W':
        ry--;
        break;
    case 'S':
        rx++;
        break;
    case 'E':
        ry++;
        break;
    case 'N':
        rx--;
        break;
    case 'T':
        return true;
    }
    if (cells[rx][ry] < 0)
    {
        die("Invalid move");
    }
    return false;
}

int main()
{
    std::string line;
    std::getline(std::cin, line);
    std::istringstream line_ss(line);
    assert((line_ss >> H >> W) && (line_ss >> std::ws).eof());
    cells.resize(H + 2, std::vector<int>(W + 2));
    for (int j = 0; j <= W + 1; j++)
    {
        cells[0][j] = cells[H + 1][j] = -2;
    }
    for (int i = 1; i <= H; i++)
    {
        cells[i][0] = cells[i][W + 1] = -2;
        std::getline(std::cin, line);
        line_ss.str(line);
        line_ss.clear();
        for (int j = 1; j <= W; j++)
        {
            bool cell;
            line_ss >> cell;
            cells[i][j] = cell ? -1 : 0;
        }
        assert(line_ss && (line_ss >> std::ws).eof());
    }
    program_pulibot();
    output.open("robot.bin", std::ios::binary);
    output.put(H).put(W);
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            output.put(cells[i][j]);
        }
    }
    bool done = false;
    int steps = 0;
    while (!done && ++steps <= MAX_STEPS)
    {
        std::vector<int> state = {
            cells[rx][ry],
            cells[rx][ry - 1],
            cells[rx + 1][ry],
            cells[rx][ry + 1],
            cells[rx - 1][ry]};
        for(auto i : state) cout << i << " ";
        cout << el;
        instruction instr = program[encode_state(state)];
        output.put(encode_instr(instr));
        if (!instr.action)
        {
            for(auto i : state) cout << i << " ";
            cout << el;
            die("Unexpected state");
        }
        done = step(instr);
    }
    cout << steps << el;
    if (!done)
    {
        output.put(0xE0);
        die("Too many steps");
    }
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            std::cout << std::setw(2) << cells[i][j] << (j == W ? "\n" : " ");
        }
    }
}
*/

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