Submission #863628

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
863628	2023-10-20 16:06:10	neki	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	860 KiB

prison

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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