Submission #629587

#	Time	Username	Problem	Language	Result	Execution time	Memory
629587		qwerasdfzxcl	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	14 ms	1108 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct Range{
    int l, r, x;
    Range(){}
    Range(int _l, int _r, int _x): l(_l), r(_r), x(_x) {}
    bool operator<(const Range &R) const{return l < R.l;}
};
int n, dp[5050], nxt[5050], nX[5050];
vector<int> L, X;
vector<Range> V[33];

void calc_optimal(int n){
    for (int i=3;i<=n;i++){
        dp[i] = 1e9;
        for (int j=1;j<=min(i-2, 20);j++){
            int tmp = (i-3) / j + 1;
            if (dp[i] > dp[tmp] + j){
                dp[i] = dp[tmp] + j;
                nxt[i] = tmp;
                nX[i] = j;
            }
        }
    }

    while(n>=3){
        L.push_back(n);
        X.push_back(nX[n]);
        n = nxt[n];
    }


    /*for (auto &x:L) printf("%d ", x);
    printf("\n");
    for (auto &x:X) printf("%d ", x);
    printf("\n");*/
    //exit(0);
}

std::vector<std::vector<int>> devise_strategy(int N) {
    n = N;
    calc_optimal(n);

    int ans[2] = {-1, -2};
    vector<vector<int>> ret;

    V[0].emplace_back(1, n, 0);
    V[1].emplace_back(1, n, 0);
    int s = 0;

    for (int step=0;step<=(int)L.size();step++){
        int px = step==0?1:X[step-1];
        int cx = step==(int)L.size()?1:X[step], typ = step&1;

        for (int i=s;i<s+px;i++){
            //printf("YES %d\n", i);
            ret.emplace_back(n+1);
            ret[i][0] = typ;

            int pt = 0;

            for (auto &[l, r, x]:V[step]){
                ret[i][l] = ans[typ];
                ret[i][r] = ans[typ^1];

                int cnt = 0;

                while(pt<(int)V[step+1].size() && V[step+1][pt].l>=l && V[step+1][pt].r<=r){
                    if (V[step+1][pt].x!=i) {pt++; continue;}

                    cnt++;
                    int ll = V[step+1][pt].l, rr = V[step+1][pt].r;
                    //printf(" %d %d\n", ll, rr);

                    for (int j=l;j<=ll;j++) ret[i][j] = ans[typ];
                    for (int j=rr;j<=r;j++) ret[i][j] = ans[typ^1];

                    if (rr-ll+1 <= 2) {pt++; continue;}
                    int cd = (rr-ll-2) / cx + 1, pos = ll+1;
                    for (int t=0;t<cx;t++){
                        V[step+2].emplace_back(pos, min(pos+cd-1, rr-1), s+px+t);
                        for (int j=V[step+2].back().l;j<=V[step+2].back().r;j++) ret[i][j] = V[step+2].back().x;

                        pos += cd;
                        if (pos>=rr) break;
                    }
                    pt++;
                }

                assert(cnt<=1);
            }
        }

        sort(V[step+2].begin(), V[step+2].end());

        s += px;
    }


    //for (auto &v:ret) {for (auto &x:v){if (x>=0) printf("%d ", x); else printf("%c ", x==-1?'A':'B');} printf("\n");}
    //exit(0);

    return ret;
}

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