Submission #1243299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243299		badge881	Prisoner Challenge (IOI22_prison)	C++20	100 / 100	7 ms	1096 KiB

prison

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

vector<vector<int>> devise_strategy(int size_limit)
{
    const int MAXN = 5000;
    const vector<int> counts = {2, 3, 3, 3, 3, 2, 2, 2};
    const vector<int> levels = {5000, 2499, 833, 277, 92, 30, 14, 6, 2};
    const int depth = counts.size();

    auto transform = [&](int x, int stage)
    {
        for (int i = 1; i <= stage; ++i)
        {
            if (x <= 1)
                return 1;
            x = (x - 2) % levels[i] + 1;
        }
        return x;
    };

    vector<vector<int>> strat;
    vector<int> base(MAXN + 1);
    base[0] = 0;

    for (int i = 1; i <= MAXN; ++i)
    {
        int v = transform(i, 0);
        if (v == 1)
            base[i] = -1;
        else if (v == levels[0])
            base[i] = -2;
        else
            base[i] = (v - 2) / levels[1] + 1;
    }

    strat.push_back(base);

    for (int stage = 0; stage < depth; ++stage)
    {
        int turn = (stage & 1) ^ 1;
        int win = turn == 0 ? -1 : -2;
        int lose = -3 - win;
        int offset = strat.size() + counts[stage];

        for (int opp = 0; opp < counts[stage]; ++opp)
        {
            vector<int> row(MAXN + 1);
            row[0] = turn;

            for (int i = 1; i <= MAXN; ++i)
            {
                int val = transform(i, stage);
                if (val == 1)
                {
                    row[i] = win;
                }
                else if (val == levels[stage])
                {
                    row[i] = lose;
                }
                else
                {
                    int id = (val - 2) / levels[stage + 1];
                    if (id < opp)
                        row[i] = win;
                    else if (id > opp)
                        row[i] = lose;
                    else
                    {
                        int next = transform(i, stage + 1);
                        if (next == 1)
                            row[i] = win;
                        else if (next == levels[stage + 1])
                            row[i] = lose;
                        else
                        {
                            if (stage + 2 > depth)
                            {
                                row[i] = -1;
                            }
                            else
                            {
                                int next_id = (next - 2) / levels[stage + 2];
                                row[i] = next_id + offset;
                            }
                        }
                    }
                }
            }

            strat.push_back(row);
        }
    }

    for (auto &row : strat)
    {
        row.resize(size_limit + 1);
        for (int &x : row)
            x = clamp(x, -2, (int)strat.size() - 1);
    }

    return strat;
}

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