Submission #833847

#	Time	Username	Problem	Language	Result	Execution time	Memory
833847		pavement	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	340 KiB

prison

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

#define mp make_pair

using ii = pair<int, int>;

vector<vector<int> > devise_strategy(int N) {
    auto ceil_log = [&](int n, int k) {
        int ret = 0, tmp = 1;
        while (tmp < n) {
            tmp *= k;
            ret++;
        }
        return ret;
    };

    int min_sf = (int)1e9, base = -1, b = -1;

    for (int i = 2; i <= N; i++) {
        int j = ceil_log(N - 1, i);
        if (min_sf > (i + 1) * j - 1) {
            min_sf = (i + 1) * j - 1;
            base = i;
            b = j;
        }
    }

    int x = min_sf;
    vector<vector<int> > s(x + 1, vector<int>(N + 1));

    auto unpack = [&](int v) {
        int b_bit = v / (base + 1), state = v % (base + 1);
        return mp(b - b_bit, state);
    };

    auto pack = [&](int bit, int state) {
        int tmp = (b - bit) * (base + 1) + state;
        assert(0 <= tmp && tmp <= x);
        return tmp;
    };

    auto get_digit = [&](int num, int pos) {
        while (pos--) {
            num /= base;
        }
        return num % base;
    };

    for (int i = 0; i <= x; i++) {
        auto [bit, state] = unpack(i);
        if (state == 0) {
            s[i][0] = 0;
            for (int j = 1; j <= N; j++) {
                // find digit at position bit of j
                int digit = get_digit(j - 1, bit);
                assert(0 <= digit && digit < base);
                // write (bit, digit + 1)
                s[i][j] = pack(bit, digit + 1);
            }
        } else {
            s[i][0] = 1;
            for (int j = 1; j <= N; j++) {
                // find digit at position bit of j
                int digit = get_digit(j - 1, bit);
                if (digit == state - 1) {
                    if (bit == 0) {
                        s[i][j] = 0;
                    } else {
                        // write (bit - 1, 0)
                        s[i][j] = pack(bit - 1, 0);
                    }
                } else if (digit > state - 1) {
                    s[i][j] = -1;
                } else {
                    s[i][j] = -2;
                }
            }
        }
    }
    return s;
}

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