Submission #1273563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273563		hubertm	Prisoner Challenge (IOI22_prison)	C++20	100 / 100	18 ms	7272 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> segments[8];
vector<int> steps = { 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4 ,4, 5, 5, 5, 6, 6, 6, 7, 7};
int t[8];

void createSegments(int l, int r, int level)
{
    t[level] = max(t[level], r - l + 1);
    segments[level].emplace_back(l, r);
    ++l; --r;

    if (level == 7) return;

    int len = r - l + 1;

    if (level <= 5)
    {
        int k = len / 3;
        int a = l + k - 1;
        int b = a + k;
        if (len % 3 == 2) ++b;

        createSegments(l, a, level + 1);
        createSegments(a + 1, b, level + 1);
        createSegments(b + 1, r, level + 1);
    }
    else
    {
        createSegments(l, l + len / 2 - 1, level + 1);
        createSegments(l + len / 2, r, level + 1);
    }
}

vector<vector<int>> devise_strategy(int N)
{
    createSegments(1, 5000, 0);

    vector<vector<int>> strategy;
    for (int n = 0; n <= 20; ++n)
    {
        vector<int> current(N + 1);

        int step = steps[n];

        current[0] = (step & 1);

        for (int j = 1; j <= N; ++j)
        {
            pair<int, int> segment = make_pair(1e9, 1e9);
            int idx = 0;

            for (int i = 0; i < segments[step].size(); ++i)
            {
                if (segments[step][i].second >= j)
                {
                    segment = segments[step][i];

                    if (step == 7) idx = i % 2;
                    else idx = i % 3;
                    break;
                }
            }

            if (segment.first > j)
            {
                for (int i = 0; i < segments[step - 1].size(); ++i)
                {
                    if (segments[step - 1][i].second >= j)
                    {
                        segment = segments[step - 1][i];
                        break;
                    }
                }

                if (j == segment.first)
                {
                    if (step & 1)
                        current[j] = -2;
                    else
                        current[j] = -1;
                    continue;
                }
                if (j == segment.second)
                {
                    if (step & 1)
                        current[j] = -1;
                    else
                        current[j] = -2;
                    continue;
                }

                continue;
            }

            if (step > 0)
            {
                int written;
                if (step == 7) written = (n - 1) % 2;
                else written = (n - 1) % 3;

                if (idx < written)
                {
                    if (step & 1)
                        current[j] = -2;
                    else
                        current[j] = -1;
                    continue;
                }
                if (idx > written)
                {
                    if (step & 1)
                    current[j] = -1;
                    else
                        current[j] = -2;
                    continue;
                }
            }

            if (j == segment.first)
            {
                if (step & 1)
                    current[j] = -2;
                else
                    current[j] = -1;
                continue;
            }
            if (j == segment.second)
            {
                if (step & 1)
                    current[j] = -1;
                else
                    current[j] = -2;
                continue;
            }

            for (int i = 0; i < segments[step + 1].size(); ++i)
            {
                if (segments[step + 1][i].second >= j)
                {
                    segment = segments[step + 1][i];

                    if (step == 6) idx = i % 2;
                    else idx = i % 3;
                    break;
                }
            }

            current[j] = step * 3 + idx + 1;
        }

        strategy.push_back(current);
    }

    return strategy;
}

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