Submission #1140394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140394		efishel	Prisoner Challenge (IOI22_prison)	C++20	56 / 100	8 ms	1352 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>;

vvi devise_strategy (int n) {
    vvi ans;
    {vi row;
    row.push_back(0);
    for (ll j = 1; j <= n; j++) {
        row.push_back(j>>12&1 ? 14 : 1);
    }
    ans.push_back(row);}
    for (ll i = 1; i <= 13; i++) { // bit-th bit of !openB is 0
        ll bit = 13-i;
        bool openB = i%2;
        vi row;
        row.push_back(openB);
        for (ll j = 1; j <= n; j++) {
            assert(row.size() == j);
            if (j>>bit&1) row.push_back(openB ? -1 : -2);
            else row.push_back(j>>(bit-1)&1 ? i+14 : i+1);
        }
        for (int &j : row) if (j >= 13+14) j = -2;
        ans.push_back(row);
    }
    for (ll i = 1; i <= 13; i++) { // bit-th bit of !openB is 1
        ll bit = 13-i;
        bool openB = i%2;
        vi row;
        row.push_back(openB);
        for (ll j = 1; j <= n; j++) {
            if (!(j>>bit&1)) row.push_back(openB ? -2 : -1);
            else row.push_back(j>>(bit-1)&1 ? i+14 : i+1);
        }
        for (int &j : row) if (j >= 13+14) j = -2;
        ans.push_back(row);
    }
    return ans;
}

/*
0: start

1: 12th bit A 0
2: 11th bit B 0
3: 10th bit A 0
...
13: 0th bit A 0

14: 12th bit A 1
15: 11th bit B 1
16: 10th bit A 1
...
26: 0th bit A 1
*/

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