Submission #863661

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

prison

#include "prison.h"
#include <bits/stdc++.h>
#define ll int
#define vc vector

using namespace std;

#include <vector>

std::vector<std::vector<int>> devise_strategy(int N) {
  vc<ll>dp(22);dp[0]=1;
  vc<ll>best(22, -1);//todo best for 0 and 1
  for(ll x=1;x<=21;++x){
    for(ll j=0;x-j-1>=0;++j) if(dp[x]<2+j*dp[x-j])dp[x]=2+j*dp[x-j], best[x]=j;
  }
  vc<vc<ll>> ans(21, vc<ll>(N+1, -1));
  
  function<void (ll, ll, ll, ll, ll, ll)> sim=[&](ll l, ll r, ll ab, ll x, ll pos, ll nxt){
    assert(pos<21);
    
    ans[pos][0]=ab;
    ans[pos][l]=-1-(ab);
    ans[pos][r]=-1-(!ab);
    ++l,--r;

    ll ch=dp[x-best[x]];
    for(ll il=l, ir=min(r,il+ch-1), cnt=0;il<=r;il+=ch, ++cnt){
      ir=min(r,il+ch-1);
      //cerr<<l<<" "<<r<<" "<<il<<" "<<ir<<" " << ch<<endl;
      assert(ir-il+1<=ch);
      for(ll i=il;i<=ir;++i){
        ans[pos][i]=nxt+cnt;
      }
      for(ll i=l-1;i<=r+1;++i){
        assert(nxt+cnt<21);
        if(i<il)ans[nxt+cnt][i]=-1-(!ab);
        if(ir<i)ans[nxt+cnt][i]=-1-(ab);
      }
      sim(il, ir, !ab, x-best[x], nxt+cnt, nxt+best[x]);
    }
  };
  sim(1, N, 0, 21, 0, 1);
  for(ll i=0;i<21;++i)if(ans[i][0]==-1) ans[i][0]=0;
  return ans;
}

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