Submission #863628

#	Time	Username	Problem	Language	Result	Execution time	Memory
863628		neki	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	860 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=1;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(ans[pos][0]==-1 or ans[pos][0]==ab);
    ans[pos][0]=ab;

    ans[pos][l]=-1-(ab);
    ans[pos][r]=-1-(!ab);
    ++l,--r;
    if(l>r) return;

    ll ch=dp[x-best[x]];
    for(ll il=l, ir=min(r,l+ch-1), cnt=0;il<=r;il+=ch,ir+=min(r, ir+ch), ++cnt){
      for(ll i=il;i<=ir;++i){
        ans[pos][i]=nxt+cnt;
      }
      for(ll i=l-1;i<=r+1;++i){
        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;
  /*cout<< N<<endl;
  for(auto v: ans){
    for(auto u: v){
      cout<< u <<" ";
    }
    cout<<endl;
  }*/
  return ans;
}

/*int main(){
  for(auto v: devise_strategy(8)){
    for(auto u: v){
      cout<< u <<" ";
    }
    cout<<endl;
  }
}*/

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