Submission #1244294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244294		duckindog	Prisoner Challenge (IOI22_prison)	C++20	90 / 100	7 ms	1608 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

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

    if (r - l - 1 <= 0) return;
    if (r - l - 1 == 1) { 
        dnc(id, stage + 1, 1, l, r, l + 1, r - 1);
        return;
    }
    if (r - l - 1 <= 2) { 
        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) {
    f.assign(22, 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 f;
}

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