Submission #1064274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064274		hotboy2703	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	348 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(23,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 <= 22;i ++){
        res[i][0] = !((i/2)&1);
        for (ll j = 1;j <= n;j ++){
            ll l = 1,r = n;
            for (ll k = 0;k <= i/2;k ++){
                if (r-l <= 1){
                    r = l-1;
                    break;
                }
                
                if (k==i/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 (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/2+1)*2+j>(l+r)/2;
            }
        }
    }

    return res;
}

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