Submission #1021970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021970		ProtonDecay314	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1116 KiB

prison

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
#include "prison.h"

const int CHOOSE_A = 0, CHOOSE_B = 1;
const int GUESS_A = -1, GUESS_B = -2;

void make_strat(const vi& dp, const vi& opt_divider, vvi& s, int bag_to_choose, int l, int r, int x, int next_avail) {
    assert(x <= 20);

    int n = r - l + 1;

    s[x][0] = bag_to_choose;

    s[x][l] = (bag_to_choose == CHOOSE_A ? GUESS_A : GUESS_B);
    s[x][r] = (bag_to_choose == CHOOSE_A ? GUESS_B : GUESS_A);

    // ! TODO once you recurse, also update the strategy for the sublevels
    if(n > 2) {
        // Assume it's going to be perfectly divided (N = 5588 guarantees it anyways)
        int divisions = opt_divider[n];

        vi sizes_pref(divisions + 1, l + 1);

        LI(i, 0, divisions) {
            sizes_pref[i + 1] = sizes_pref[i] + (n - 2) / divisions;
        }

        LI(i, 0, divisions) {
            int divl = sizes_pref[i], divr = sizes_pref[i + 1] - 1;
            LI(j, l, divl) {
                s[next_avail + i][j] = (bag_to_choose == CHOOSE_A ? GUESS_B : GUESS_A);
            }

            LI(j, divr + 1, r + 1) {
                s[next_avail + i][j] = (bag_to_choose == CHOOSE_A ? GUESS_A : GUESS_B);
            }

            LI(j, divl, divr + 1) {
                s[x][j] = next_avail + i;
            }

            make_strat(dp, opt_divider, s, 1 - bag_to_choose, divl, divr, next_avail + i, next_avail + divisions);
        }
    }
}

vvi devise_strategy(int N) {
    // DP
    int maxn = 5588;
    vi dp(maxn + 1, INF(int));

    vi opt_divider(maxn + 1, 0);

    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 0;
    
    LI(i, 3, maxn + 1) {
        dp[i] = dp[(i - 2 - 1) / 3 + 1] + 3;
        opt_divider[i] = 3;

        if(dp[(i - 2 - 1) / 2 + 1] + 2 <= dp[i]) opt_divider[i] = 2;

        dp[i] = min(dp[i], dp[(i - 2 - 1) / 2 + 1] + 2);

        if(dp[i - 2] + 1 <= dp[i]) opt_divider[i] = 1;

        dp[i] = min(dp[i], dp[i - 2] + 1);
    }

    // LI(i, 0, maxn + 1) {
    //     cout << i << " " << dp[i] << " " << opt_divider[i] << endl;
    // }

    // Strat building

    vvi s;
    for(int i = 0; i <= 20; i++) {
        vi sr(maxn + 1, 0);
        s.pb(sr);
    }

    make_strat(dp, opt_divider, s, CHOOSE_A, 1, maxn, 0, 1);

    for(int i = 0; i <= 20; i++) {
        LI(j, 0, maxn - N) s[i].pop_back(); // Keep popping until the array is of the correct size
    }

    return s;
}

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