Submission #625989

#	Time	Username	Problem	Language	Result	Execution time	Memory
625989		I_love_Hoang_Yen	Prisoner Challenge (IOI22_prison)	C++17	48.50 / 100	21 ms	1388 KiB

prison

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

int p3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};

// base 3
int get_bit(int n, int bit) {
    return (n % p3[bit + 1]) / p3[bit];
}

const int NBIT = 8;
std::pair<int,int> decode(int encoded) {
    return {
        NBIT - encoded / 4 - 1,
        encoded % 4,
    };
}

int encode(int bit, int t) {
    if (bit < 0) return 0;
    return (NBIT - bit - 1) * 4 + t;
}

std::vector<std::vector<int>> devise_strategy(int n) {
    const int NSTATE = NBIT * 4;
    std::vector<std::vector<int>> res(NSTATE, std::vector<int> (n+1, 0));

    for (int state = 0; state < NSTATE; ++state) {
        auto [bit, t] = decode(state);
        if (t == 0) res[state][0] = 0;
        else res[state][0] = 1;

        for (int i = 1; i <= n; ++i) {
            int cur_bit = get_bit(i, bit);

            if (t == 0) {
                res[state][i] = encode(bit, cur_bit + 1);
            } else {
                int a_bit = t - 1;
                int b_bit = get_bit(i, bit);

                if (a_bit < b_bit) res[state][i] = -1;
                else if (a_bit > b_bit) res[state][i] = -2;
                else res[state][i] = encode(bit - 1, 0);
            }
        }
    }

    return res;
}

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