Submission #1072367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072367		vjudge1	Prisoner Challenge (IOI22_prison)	C++17	38 / 100	12 ms	1740 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
using vi = vector <int>;
using vvi = vector <vi>;

vi solve (ll n, ll num) {
    vi si(n+1, -15);
    if (0 <= num && num <= 12) { // you start at bit 12-x
        ll bit = 12-num;
        si[0] = 0; // open a
        for (ll a = 1; a <= n; a++) {
            if (a>>bit&1) si[a] = 13+bit; // a has bit bit on
            else si[a] = 26+bit; // a has bit bit off
        }
    } else if (13 <= num && num <= 25) { // a has bit x-13 on
        ll bit = num-13;
        si[0] = 1; // open b
        for (ll b = 1; b <= n; b++) {
            if (b>>bit&1) si[b] = 12-(bit-1); // you start at bit-1
            else si[b] = -2; // b has less
        }
    } else if (26 <= num && num <= 38) { // a has bit x-26 off
        ll bit = num-26;
        si[0] = 1; // open b
        for (ll b = 1; b <= n; b++) {
            if (b>>bit&1) si[b] = -1; // a has less
            else si[b] = 12-(bit-1); // you start at bit-1
        }
    } else assert(false);
    return si;
}

vvi devise_strategy (int n) {
    vvi ans(39);
    for (ll i = 0; i < 39; i++) ans[i] = solve(n, i);
    return ans;
}

/*
messages:
you start at bit [0..12] (0 <= x <= 12) => (12-x)
a has bit [0..12] on (13 <= x <= 25) => (x-13)
a has bit [0..12] off (26 <= x <= 38) => (x-26)
// the answer is a (x = 39)
// the answer is b (x = 40)
*/

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