Submission #1230040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230040		badge881	Prisoner Challenge (IOI22_prison)	C++20	41 / 100	10 ms	1608 KiB

prison

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

const int iTakeA = -1, iTakeB = -2;
vector<vector<int>> devise_strategy(int N)
{
    vector<vector<int>> result(37, vector<int>(N + 1, 0));
    int power = 12;
    for (int i = 0; i < 12; i++)
    {
        for (int j = 1; j <= N; j++)
            if (j & (1 << power))
                result[i][j] = 13 + i;
            else
                result[i][j] = 25 + i;
        power--;
    }
    // cas final on verifie la pow 0 (0 ou 1) et on decide directement car forcement differents
    for (int j = 1; j <= N; j++)
        if (j % 2 == 0)
            result[12][j] = iTakeA; // prend sac A
        else
            result[12][j] = iTakeB; // prend sac B

    power = 12;
    for (int i = 13; i < 25; i++)
    {
        // sac A a la power `power` active
        result[i][0] = 1;
        for (int j = 1; j <= N; j++)
            if (j & (1 << power))
                result[i][j] = i - 12;
            else
                result[i][j] = iTakeB; // prend sac B
        power--;
    }
    power = 12;
    for (int i = 25; i < 37; i++)
    {
        // sac A a la power `power` disactive
        result[i][0] = 1;
        for (int j = 1; j <= N; j++)
            if (j & (1 << power))
                result[i][j] = iTakeA; // prend sac A
            else
                result[i][j] = i - 24;
        power--;
    }

    return result;
}

#ifdef HOME
int main()
{
    int N = 5000;

    vector<vector<int>> result = devise_strategy(N);

    // for (int i = 0; i < 37; i++)
    // {
    //     cout << "I read " << i << " on board, I will see bag " << result[i][0] << " and write on board: ";
    //     for (int j = 1; j <= N; j++)
    //         cout << result[i][j] << " ";
    //     cout << endl;
    // }
    random_device rd;
    uniform_int_distribution<> dis(1, N);
    int distribution = 0;
    for (int sacA = 1; sacA <= N; sacA++)
        for (int sacB = 1; sacB <= N; sacB++)
        {
            int tab = 0;
            if (sacA == sacB)
                continue;
            while (tab >= 0)
                if (result[tab][0] == 0)
                    tab = result[tab][sacA];
                else
                    tab = result[tab][sacB];
            if ((tab == iTakeA && sacA < sacB) or (tab == iTakeB && sacA > sacB))
                distribution += sacA < sacB ? 1 : -1;
            else
                cout << "I lose! A = " << sacA << " B = " << sacB << endl;
        }

    return 0;
}
#endif

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