Submission #1213026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213026		omsincoconut	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	7 ms	1096 KiB

prison

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> blocksize;
vector<vector<int>> block;

/*
0) 5000 -> 1666
1) 1666 -> 555
2) 555 -> 185
3) 185 -> 61
4) 61 -> 20

5) 20 -> 9
6) 9 -> 4

7) 4 -> 2

8) 2 -> 1
*/

const int MAX_CAN = 5000;
void genblock(int l = 1, int r = MAX_CAN, int ly = 0) {
    while (blocksize.size() <= ly) blocksize.push_back(0);
    while (block.size() <= ly) block.push_back(vector<int>(MAX_CAN+1));

    if (ly <= 4) {
        blocksize[ly] = 3;

        int e1 = l+(r-l)/3;
        int e2 = l+2*(r-l)/3;

        for (int i = l+1; i <= e1; i++) block[ly][i] = 0;
        for (int i = e1+1; i <= e2; i++) block[ly][i] = 1;
        for (int i = e2+1; i < r; i++) block[ly][i] = 2;

        block[ly][l] = -1;
        block[ly][r] = -2;

        genblock(l+1, e1, ly+1);
        genblock(e1+1, e2, ly+1);
        genblock(e2+1, r-1, ly+1);
    } else if (ly <= 6) {
        blocksize[ly] = 2;

        int e = (l+r)/2;
        for (int i = l+1; i <= e; i++) block[ly][i] = 0;
        for (int i = e+1; i < r; i++) block[ly][i] = 1;

        block[ly][l] = -1;
        block[ly][r] = -2;

        genblock(l+1, e, ly+1);
        genblock(e+1, r-1, ly+1);
    } else if (ly == 7) {
        blocksize[ly] = 1;

        for (int i = l+1; i < r; i++) block[ly][i] = 0;

        block[ly][l] = -1;
        block[ly][r] = -2;
        genblock(l+1, r-1, ly+1);
    } else if (ly == 8) {
        blocksize[ly] = 0;

        block[ly][l] = -1;
        block[ly][r] = -2;
    }
}

vector<vector<int>> devise_strategy(int _N) {
    N = _N;
    genblock();

    int x = 20;
    vector<vector<int>> ret(x+1, vector<int>(N+1));

    // First play
    ret[0][0] = 0;
    for (int i = 1; i <= N; i++) ret[0][i] = 1 + block[0][i];
    ret[0][1] = -1;
    ret[0][N] = -2;

    // Other plays
    vector<vector<int>> state_description = {
        {-1, 0},
        {0, 0},
        {0, 1},
        {0, 2},
        {1, 0},
        {1, 1},
        {1, 2},
        {2, 0},
        {2, 1},
        {2, 2},
        {3, 0},
        {3, 1},
        {3, 2},
        {4, 0},
        {4, 1},
        {4, 2},
        {5, 0},
        {5, 1},
        {6, 0},
        {6, 1},
        {7, 0}
    };

    for (int j = 1; j <= 20; j++) {
        int from_layer = state_description[j][0];
        int from_block = state_description[j][1];

        int cur_player = 1 - from_layer%2;
        ret[j][0] = cur_player;

        for (int i = 1; i <= N; i++) {
            int to_layer = from_layer+1;
            int to_block = block[to_layer][i];
            int cur_block = block[from_layer][i];

            if (i == 1) ret[j][i] = -1 - cur_player;
            else if (i == N) ret[j][i] = -1 - (1-cur_player);
            else if (cur_block == -1) ret[j][i] = -1 - cur_player;
            else if (cur_block == -2) ret[j][i] = -1 - (1-cur_player);
            else if (cur_block < from_block) ret[j][i] = -1 - cur_player;
            else if (from_block < cur_block) ret[j][i] = -1 - (1-cur_player);
            else if (to_block == -1) ret[j][i] = -1 - cur_player;
            else if (to_block == -2) ret[j][i] = -1 - (1-cur_player);
            else {
                vector<int> to_find = {to_layer, to_block};
                int idx = find(state_description.begin(), state_description.end(), to_find) - state_description.begin();
                if (idx <= x) ret[j][i] = idx;
                else ret[j][i] = -1;
            }
        }
    }

    return ret;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 90 / 90