Submission #629601

#	Time	Username	Problem	Language	Result	Execution time	Memory
629601		4123xr4323	Prisoner Challenge (IOI22_prison)	C++17	41 / 100	25 ms	1492 KiB

prison

#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(),a.end()
using namespace std;
using pii = pair <long long, long long>;
constexpr int maxn = 1e5 + 10;
constexpr long long inf = 1e17 + 10;

vector <vector <int>> devise_strategy (int N) {
    vector <vector <int>> res = {};
    int x = 0, n = N;
    while (N) ++x, N >>= 1;
    int S = x - 1;
    x = x * 3 - 2;
    res.resize (x);
    for (int i = 0; i < x - 1; ++i) {
        res[i].resize (n + 1);
        res[i][0] = (i % 3) > 0;
        int b = S - (i / 3);
        if ((i % 3) == 0) {
            for (int j = 1; j <= n; ++j) {
                res[i][j] = i + 1 + (j >> b & 1);
            }
            continue;
        }
        int h = i - (i / 3) * 3 - 1;
        for (int j = 1; j <= n; ++j) {
            if ((j >> b & 1) == h) res[i][j] = (i / 3) * 3 + 3;
            else if (j >> b & 1) res[i][j] = -1;
            else res[i][j] = -2;
        }
    }
    res[x - 1].resize (n + 1);
    res[x - 1][0] = 0;
    int b = S - ((x - 1) / 3);
    for (int j = 1; j <= n; ++j) {
        if (j >> b & 1) res[x - 1][j] = -2;
        else res[x - 1][j] = -1;
    }
    return res;
}

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