Submission #1272311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272311		hubertm	Prisoner Challenge (IOI22_prison)	C++20	56 / 100	11 ms	7548 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

constexpr int maxBit = 12;
constexpr int x = (maxBit + 1) * 2;

int getStep(int n)
{
    return (n + 1) / 2;
}

vector<vector<int>> devise_strategy(int N)
{
    vector<vector<int>> strategy;
    for (int n = 0; n <= x; ++n)
    {
        vector<int> current(N + 1);
        int step = getStep(n);

        current[0] = (step & 1);

        for (int j = 1; j <= N; ++j)
        {
            bool v = j & (1 << (maxBit - step + 1));

            bool written = !(n & 1);

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

            if (step == maxBit + 1) continue;

            v = j & (1 << (maxBit - step));

            current[j] = step * 2 + v + 1;
        }

        strategy.push_back(current);
    }

    // for (int i = 0; i <= x; ++i)
    // {
    //     for (int v : strategy[i]) cout << v << ' ';
    //     cout << '\n';
    // }

    return strategy;
}

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