Submission #723248

#	Time	Username	Problem	Language	Result	Execution time	Memory
723248		Luicosas	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	980 KiB

prison

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#define prv(x) for(auto& pval : x) cout << pval << " "; cout << "\n";
#ifdef LOC
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n";
#else 
#define debug(...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> 
ostream& operator << (ostream& out, vector<T> v) {
    for(auto& i : v) {
        out << i << " ";
    }
    return out;
}

std::vector<std::vector<int>> devise_strategy(int n) {
    vector<vector<int>> strat(21, vector<int>(n + 1, 0));
    
    vector<int> lens{3, 3, 3, 3, 3, 2, 2, 1};
    vector<int> idxs{1, 4, 7, 10, 13, 16, 18, 20, 21};
    for(int i = 0; i < sz(lens); i++) {
        assert(idxs[i + 1] == idxs[i] + lens[i]);
    }
    
    // assign lookups
    strat[0][0] = 0;
    for(int i = 0; i < sz(lens); i++) {
        for(int ii = idxs[i]; ii < idxs[i] + lens[i]; ii++) {
            strat[ii][0] = (i ^ 1) & 1;
        }
    }

    // assign connections
    const int a_small = -1, b_small = -2;
    function<void(int,int,int,int)> dfs = [&](int l, int r, int idx, int nlayer) {
        int is_a = (strat[idx][0] == 0);
        if(l >= 0 && l < n + 1) {
            strat[idx][l] = (is_a ? a_small : b_small);
        }
        if(r >= 0 && r < n + 1) {
            strat[idx][r] = (is_a ? b_small : a_small);
        }

        if(l + 1 == r) {
            return;
        }

        int nlen = (r - l - 1) / lens[nlayer]; 
        assert((r - l - 1) % lens[nlayer] == 0);
        for(int i = 0; i < lens[nlayer]; i++) {
            int nl = l + 1 + nlen * i, nr = l + nlen * (i + 1);
            for(int ii = nl; ii <= nr; ii++) {
                if(ii >= 0 && ii < n + 1) {
                    strat[idx][ii] = idxs[nlayer] + i;
                }
            }
            for(int ii = l; ii < nl; ii++) {
                if(ii >= 0 && ii < n + 1) {
                    strat[idxs[nlayer] + i][ii] = (is_a ? b_small : a_small);
                }
            }
            dfs(nl, nr, idxs[nlayer] + i, nlayer + 1);
            for(int ii = nr + 1; ii <= r; ii++) {
                if(ii >= 0 && ii < n + 1) {
                    strat[idxs[nlayer] + i][ii] = (is_a ? a_small : b_small);
                }
            }
        }
    };
    dfs(1, 5588, 0, 0);

    return strat;
}

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