Submission #1267318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267318		silentloop	Prisoner Challenge (IOI22_prison)	C++20	0 / 100	0 ms	328 KiB

prison

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

int con(ll x) {
    if (x == 1) return 2;
    return 1;
}

vector<vector<int>> devise_strategy(int N) {
    ll i, j, ab = 1, bit = 7, sig = 1, val, tam = 22, aBit, aVal;

    // pot[k] = 3^k
    vector<int> pot(9, 1);
    for (i = 1; i <= bit; i++) pot[i] = pot[i - 1] * 3;

    vector<vector<int>> ans(tam, vector<int>(N + 1, 0));

    // definir qué bolsa mira cada estado
    for (i = 1; i < tam; i += 3) {
        for (j = 0; j < 3 && i + j < tam; j++)
            ans[i + j][0] = ab;
        ab = con(ab + 1) - 1;
    }

    // primer nivel
    for (i = 1; i <= N; i++) {
        val = (i / pot[bit]) % 3;
        ans[0][i] = sig + val;
    }

    int aLevel = bit;
    bit--;
    sig += 3;

    // construir niveles intermedios
    for (j = 1; j < tam - 1; j++) {
        for (i = 1; i <= N; i++) {
            val = (i / pot[aLevel]) % 3;
            aVal = (j - 1) % 3;
            if (val < aVal) {
                ans[j][i] = -(ans[j][0] + 1);
            } else if (val > aVal) {
                ans[j][i] = -con(ans[j][0] + 1);
            } else {
                val = (i / pot[bit]) % 3;
                ans[j][i] = sig + val;
                // pruning del último trío:
                if (ans[j][i] == 22) { // este sería el estado "extra"
                    // en vez de ir a 22, ya decidimos directo:
                    if (val == 0)
                        ans[j][i] = -(ans[j][0] + 1);  // A más chico
                    else if (val == 2)
                        ans[j][i] = -con(ans[j][0] + 1); // B más chico
                    else
                        ans[j][i] = 21; // único estado central
                }
            }
        }
        if (j % 3 == 0) {
            aLevel = bit;
            bit--;
            sig += 3;
        }
    }

    // último estado real = 21
    for (i = 1; i <= N; i++) {
        val = i % 3;
        if (val == 0) ans[21][i] = -(ans[21][0] + 1);
        else if (val == 2) ans[21][i] = -con(ans[21][0] + 1);
        // si val == 1, en teoría no debería ocurrir que A == B,
        // así que no hay transición válida ahí
    }

    return ans;
}

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