Submission #1309967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309967		Rares	Prisoner Challenge (IOI22_prison)	C++20	100 / 100	7 ms	7268 KiB

prison

#include <bits/stdc++.h>
using namespace std;

const int MAXN=5010;
const int MAXX=21;

int idx[30][4];
vector<vector<int>> rez;
void dnc(int pId, int stage, int rcrt, int pL, int pR, int l, int r) {
    int id = idx[stage][rcrt];
    rez[id][0] = (stage & 1);
    for (int i = l; i <= r; ++i) rez[pId][i] = id;
    for (int i = pL; i <= l; ++i) rez[id][i] = -rez[id][0] - 1;
    for (int i = r; i <= pR; ++i) rez[id][i] = -2 + rez[id][0];

    if (r - l - 1 <= 0) return;
    if (r - l - 1 <= 2) {
        dnc(id, stage + 1, 1, l, r, l + 1, r - 1);
        return;
    }
    if (r - l - 1 <= 4) {
        int sz = (r - l - 2) / 2 + 1;
        dnc(id, stage + 1, 1, l, r, l + 1, l + sz);
        dnc(id, stage + 1, 2, l, r, l + sz + 1, r - 1);
        return;
    }
    int sz = (r - l - 2) / 3 + 1;
    dnc(id, stage + 1, 1, l, r, l + 1, l + sz);
    dnc(id, stage + 1, 2, l, r, l + sz + 1, r - sz - 1);
    dnc(id, stage + 1, 3, l, r, r - sz, r - 1);
}

vector<vector<int>> devise_strategy(int N) {
    rez.resize (21, vector<int> (N + 1));
    for (int i = 1, num = 0; i <= 7; ++i) {
        for (int j = 1; j <= 3; ++j) idx[i][j] = ++num;
    }
    dnc(0, 0, 0, 1, N, 1, N);

    return rez;
}

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