oj.uz

Submission #863661

# Submission time Handle Problem Language Result Execution time Memory
863661 2023-10-20T16:48:18 Z neki Prisoner Challenge (IOI22_prison) C++17
100 / 100
 9 ms 1116 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 500 KB Output is correct
8 Correct 1 ms 396 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 7 ms 856 KB Output is correct
6 Correct 9 ms 1116 KB Output is correct
7 Correct 9 ms 1104 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 4 ms 600 KB Output is correct
12 Correct 8 ms 860 KB Output is correct