Submission #1064341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064341		hotboy2703	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	8 ms	1116 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MP make_pair
#define fi first
#define se second
#define pll pair <ll,ll>
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL<<(i))
std::vector<std::vector<int>> devise_strategy(int n) {
    vector <vector<ll> > res(22,vector <ll> (n+1,0));
    res[0][0] = 0;
    res[0][1] = -1;
    res[0][n] = -2;
    for (ll j = 2;j <= n-1;j ++)res[0][j] = (j > (n+1)/2)+1;
    for (ll i = 1;i <= 21;i ++){
        res[i][0] = !(((i-1)/2)&1);
        for (ll j = 1;j <= n;j ++){
            ll l = 1,r = n;
            for (ll k = 0;k <= (i-1)/2;k ++){
                if (r-l <= 1){
                    r = l-1;
                    break;
                }
                
                if (k==(i-1)/2){
                    l++,r--;
                    ll mid=(l+r)>>1;
                    if (i&1){
                        r = mid;
                    }
                    else{
                        l = mid + 1;
                    }
                }
                else{
                    if ((k&1)==res[i][0]){
                        if (j >= r || j <= l){
                            r = l - 1;
                            break;
                        }
                    }
                    l++,r--;
                    ll mid=(l+r)>>1;
                    if (mid >= j)r = mid;
                    else l = mid + 1;
                }
            }
            // if (i==2&&j==3)cout<<l<<' '<<r<<'\n';
            if (r < l)res[i][j] = -1;
            else{
                if (j >= r)res[i][j] = -(1+(!res[i][0]));
                else if (j <= l)res[i][j] = -(1+(res[i][0]));
                else res[i][j] = ((i-1)/2+1)*2+1+(j>(l+r)/2);
            }
        }
    }
    // cout<<res[0][6]<<' '<<res[2][5]<<'\n';
    // for (ll i = 0;i <= 22;i ++){
    //     for (ll j = 0;j <= n;j ++){
    //         cout<<res[i][j]<<' ';
    //     }
    //     cout<<'\n';
    // }
    return res;
}

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