Submission #655515

#	Time	Username	Problem	Language	Result	Execution time	Memory
655515		benjaminkleyn	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	12 ms	1492 KiB

prison

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

void build(vector<vector<int>> &s, int idx, int bag, int l, int r)
{
    s[idx][0] = bag;
    s[idx][l] = - 1 - bag;
    s[idx][r] = - 2 + bag;

    if (l + 1 >= r)
        return;

    int m = (l + r) / 2;
    s[idx + 2 + (idx % 2)][r] = - 1 - bag;
    for (int i = l; i <= m; i++)
    {
        if (i > l)
            s[idx][i] = idx + 1 + (idx % 2);
        s[idx + 2 + (idx % 2)][i] = - 2 + bag;
    }

    build(s, idx + 1 + (idx % 2), 1 - bag, l, m);

    s[idx + 1 + (idx % 2)][l] = - 2 + bag;
    for (int i = m + 1; i <= r; i++)
    {
        if (i < r)
            s[idx][i] = idx + 2 + (idx % 2);
        s[idx + 1 + (idx % 2)][i] = - 1 - bag;
    }

    build(s, idx + 2 + (idx % 2), 1 - bag, m + 1, r);
}

vector<vector<int>> devise_strategy(int N)
{
    vector<vector<int>> s(61, vector<int>(N+1));
    build(s, 0, 0, 1, N);
    bool found = false;
    while (!found)
    {
        for (int x : s.back())
            if (x != 0)
                found = true;
        if (!found)
            s.pop_back();
    }
    return s;
}

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