oj.uz

Submission #1064341

# Submission time Handle Problem Language Result Execution time Memory
1064341 2024-08-18T11:40:30 Z hotboy2703 Prisoner Challenge (IOI22_prison) C++17
90 / 100
 8 ms 1116 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 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 480 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 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 #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 2 ms 348 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #3
80.0 / 90.0

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