Submission #854494

#	Time	Username	Problem	Language	Result	Execution time	Memory
854494		FilipL	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	10 ms	1368 KiB

prison

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define array_log(arr, x) {rep(y, x) {cout << arr[y] << ' ';} cout << '\n';}
#define unordered_map __gnu_pbds::gp_hash_table
using ll = long long;
const int MOD = 1e9 + 7;

#define LOCAL true

const int MAX_N = 5000 + 7;
const int MAX_X = 23;

int base3[MAX_N][9]; // idx od 1
int statetoboard[30];
int boardtostate[30];

void calc_base3() {
    rep(i, MAX_N) {
        if (i == 0) continue;
        int num = i;
        rep(di, 8) {
            base3[i][8 - di] = num % 3;
            num /= 3;
        }
    }
}
void calc_trans() {
    int board = 1;
    for (int state = 1; state < MAX_X; state++) {
        statetoboard[state] = board;
        boardtostate[board] = state;
        if (board == 7) board += 3;
        if (board == 18) board += 2;
        board++;
    }
}


vector<vector<int>> devise_strategy(int N) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector<vector<int>> strat = vector<vector<int>>(MAX_X, vector<int>(N+1, 0));
    calc_base3();
    calc_trans();

    // board == 00
    for (int num = 1; num <= N; num++) {
        strat[0][num] = boardtostate[10*base3[num][1] + 1];
    }

    for (int state = 1; state < MAX_X; state++) {
        int board = statetoboard[state];
        int d = board / 10;
        int i = board % 10;
        strat[state][0] = i % 2;
        int same = (i % 2 == 0 ? -1 : -2);
        int other = (i % 2 == 0 ? -2 : -1);
        for (int num = 1; num <= N; num++) {
            int dthis = base3[num][i];
            if (dthis < d) strat[state][num] = same;
            else if (dthis > d) strat[state][num] = other;
            else {
                strat[state][num] = boardtostate[10*base3[num][i+1] + i+1];
                if (i == 7) {
                    if (base3[num][8] == 0) strat[state][num] = same;
                    else if (base3[num][8] == 2) strat[state][num] = other;
                }
            }
        }
    }

    return strat;
}

// int main()
// {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     if (LOCAL) {
//         freopen("io/in", "r", stdin);
//         freopen("io/out", "w", stdout);
//     }

//     int N = 5000;
//     auto strat = devise_strategy(N);

//     for (int state = 0; state < MAX_X; state++) {
//         array_log(strat[state], N+1);
//     }

//     return 0;
// }

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