Submission #659094

#	Time	Username	Problem	Language	Result	Execution time	Memory
659094		mosiashvililuka	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	18 ms	1760 KiB

prison

#include<bits/stdc++.h>
#include "prison.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,dp[5009],dp2[5009],FX[5009];
vector <vector <int> > f;
map <vector <int>, bool> mp;
void rec(int q, int w, int rr, int l, int r, bool bo, int cnt, int dep){
    int i,j;
    vector <int> V;
    V.push_back(q);V.push_back(w);V.push_back(rr);V.push_back(l);V.push_back(r);V.push_back(bo);V.push_back(cnt);
    if(mp[V]==1) return;
    mp[V]=1;
    f[rr][0]=bo;
    //
    for(i=l; i<=r; i++){
        if(i<q){
            //esaa patara(bo)
            if(bo==0) f[rr][i]=-1; else f[rr][i]=-2;
            continue;
        }
        if(i>w){
            //isaa patara
            if(bo==0) f[rr][i]=-2; else f[rr][i]=-1;
            continue;
        }
        if(i==q){
            //esaa patara
            if(bo==0) f[rr][i]=-1; else f[rr][i]=-2;
            continue;
        }
        if(i==w){
            //isaa patara
            if(bo==0) f[rr][i]=-2; else f[rr][i]=-1;
            continue;
        }
        pair <int, int> p[5];int pi=0;
        int len=w-q+1;
        if(FX[dep]==0){
            FX[dep]=dp2[len];
        }
        int qw=(len-2)/FX[dep],we=(len-2)%FX[dep];
        p[0].second=q;
        for(j=1; j<=FX[dep]; j++){
            pi++;
            p[j].first=p[j-1].second+1;p[j].second=p[j].first+qw-1;
            if(j<=we) p[j].second++;
            p[j].second=min(p[j].second,w-1);
        }
        for(j=1; j<=pi; j++){
            if(p[j].first<=i&&i<=p[j].second){
                f[rr][i]=cnt+j;
                rec(p[j].first,p[j].second,cnt+j,q,w,!bo,cnt+pi,dep+1);
                break;
            }
        }
    }
}
vector<vector<int> > devise_strategy(int N) {
    a=N;
    dp[0]=0;dp[1]=dp[2]=0;
    for(i=3; i<=a; i++){
        dp[i]=i;
        for(j=2; j<=3; j++){
            c=(i-2)/j;
            if((i-2)%j!=0) c++;
            if(dp[i]>dp[c]+j){
                dp[i]=dp[c]+j;dp2[i]=j;
            }
        }
    }
    int X=dp[a]+1;
    f.resize(X);
    for(i=0; i<X; i++){
        f[i].resize(a+1);
    }
    rec(1,a,0,1,a,0,0,1);
    return f;
}

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