Submission #821530

#	Time	Username	Problem	Language	Result	Execution time	Memory
821530		finn__	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	14 ms	1028 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

constexpr int it[21] = {-1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 7},
              part[21] = {-1, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 0, 1, 0},
              d[8] = {3, 3, 3, 3, 3, 2, 2, 1},
              N_MAX = 5588;

int get_part(pair<int, int> const &range, int n, int iteration)
{
    assert(range.first + 1 <= n);
    assert(n <= range.second - 1);
    int part_size = (range.second - range.first - 1) / d[iteration];
    return (n - (range.first + 1)) / part_size;
}

pair<int, int> get_subrange(pair<int, int> const &range, int part, int iteration)
{
    int part_size = (range.second - range.first - 1) / d[iteration];
    return {range.first + 1 + part * part_size,
            range.first + (part + 1) * part_size};
}

pair<int, int> reconstruct_range(int n, int iteration)
{
    pair<int, int> range = {1, N_MAX};
    for (int i = 0; i < iteration; ++i)
    {
        if (n == range.first || n == range.second)
            return {-1, -1}; // We will never reach this state.
        range = get_subrange(range, get_part(range, n, i), i);
    }
    return range;
}

int encode_state(int iteration, int part)
{
    int state = 1;
    while (it[state] != iteration)
        ++state;
    return state + part;
}

vector<vector<int>> devise_strategy(int N)
{
    vector<vector<int>> s(21, vector<int>(N + 1));

    for (size_t i = 0; i <= 20; ++i)
    {
        s[i][0] = !(it[i] & 1);
        for (int j = 1; j <= N; ++j)
        {
            auto [a, b] = reconstruct_range(j, it[i]);

            if (a == -1 && b == -1)
                continue;

            // Check whether it's on the boundary of the common range.
            if (j == a)
            {
                s[i][j] = s[i][0] ? -2 : -1;
                continue;
            }

            if (j == b)
            {
                s[i][j] = s[i][0] ? -1 : -2;
                continue;
            }

            if (i) // In the first iteration, we don't have a subrange specified by the state.
            {
                int k = get_part({a, b}, j, it[i]);
                int h = part[i];

                // If they don't belong to the same part of the subrange, stop.
                if (k != h)
                {
                    s[i][j] = (s[i][0] ^ (k > h)) ? -2 : -1;
                    continue;
                }

                tie(a, b) = get_subrange({a, b}, h, it[i]); // the other bag's range

                // Check whether it's on the boundary of the new range.
                if (j == a)
                {
                    s[i][j] = s[i][0] ? -2 : -1;
                    continue;
                }

                if (j == b)
                {
                    s[i][j] = s[i][0] ? -1 : -2;
                    continue;
                }
            }

            assert(it[i] < 7);
            s[i][j] = encode_state(it[i] + 1, get_part({a, b}, j, it[i] + 1));
        }
    }

    return s;
}

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