Submission #628895

#	Time	Username	Problem	Language	Result	Execution time	Memory
628895		dacin21	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	14 ms	1020 KiB

prison

#include "prison.h"

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

struct Range{
    int l, r;
};

vector<vector<int>> devise_strategy(int N) {
    const int k = 20;
    vector<vector<int> > ret(k+1, vector<int>(N+1, -1));
    for(auto &e : ret) e[0] = 0;
    auto solve = [&](auto solve, int d, int val, int next_val, Range me, Range other) -> void {
        //cerr << setw(2) << d << " " << setw(2) << val << " : " << me.l << " " << me.r << " / " << other.l << " " << other.r << "\n";
        if(other.l > other.r) return;
        ret[val][0] = d%2;
        const int me_smaller = -1-(d%2);
        const int other_smaller = -1-!(d%2);
        for(int i = me.l; i <= other.l; ++i) ret[val][i] = me_smaller;
        me.l = other.l + 1;
        for(int i = other.r; i <= me.r; ++i) ret[val][i] = other_smaller;
        me.r = other.r - 1;
        if(me.l > me.r) return;

        const int BLOCK = d < 6 ? 3 :  d<7 ? 2 : 1;
        vector<pair<int, Range> > subs(BLOCK);
        for(int i=0; i<BLOCK; ++i){
            subs[i].first = next_val + i;
            subs[i].second.l = me.l + (i*(me.r-me.l+1)+BLOCK-1)/BLOCK;
            subs[i].second.r = me.l + ((i+1)*(me.r-me.l+1)+BLOCK-1)/BLOCK - 1;
            for(int j=subs[i].second.l; j<=subs[i].second.r; ++j){
                ret[val][j] = subs[i].first;
            }
        }
        for(auto &e : subs){
            solve(solve, d+1, e.first, next_val + BLOCK, other, e.second);
        }
    };

    solve(solve, 0, 0, 1, Range{1, N}, Range{1, N});
    return ret;
}

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