Submission #1140428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140428		efishel	Prisoner Challenge (IOI22_prison)	C++20	65 / 100	8 ms	1216 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) {
    vector <array <ll, 8> > base3;
    for (ll i = 0; i <= n; i++) {
        array <ll, 8> uh = { 0, 0, 0, 0, 0, 0, 0, 0 };
        ll k = i;
        for (ll j = 0; j < 8; j++) {
            uh[j] = k%3;
            k /= 3;
        }
        base3.push_back(uh);
        assert(k == 0);
    }
    vvi ans;
    {vi row;
    row.push_back(0);
    for (ll j = 1; j <= n; j++) {
        row.push_back(1 + base3[j][7]*8);
    }
    ans.push_back(row);}
    for (ll i = 1; i <= 8; i++) { // bit-th bit of !openB is 0
        ll bit = 8-i;
        bool openB = i%2;
        vi row;
        row.push_back(openB);
        for (ll j = 1; j <= n; j++) {
            if (base3[j][bit] != 0 || bit-1 < 0) row.push_back(openB ? -1 : -2);
            else row.push_back(i+1 + base3[j][bit-1]*8);
        }
        for (int &j : row) if (j >= 1+8+8+8) j = -2;
        ans.push_back(row);
    }
    for (ll i = 1; i <= 8; i++) { // bit-th bit of !openB is 1
        ll bit = 8-i;
        bool openB = i%2;
        vi row;
        row.push_back(openB);
        for (ll j = 1; j <= n; j++) {
            if (base3[j][bit] != 1 || bit-1 < 0) row.push_back((base3[j][bit] < 1)^openB ? -1 : -2);
            else row.push_back(i+1 + base3[j][bit-1]*8);
        }
        for (int &j : row) if (j >= 1+8+8+8) j = -2;
        ans.push_back(row);
    }
    for (ll i = 1; i <= 8; i++) { // bit-th bit of !openB is 2
        ll bit = 8-i;
        bool openB = i%2;
        vi row;
        row.push_back(openB);
        for (ll j = 1; j <= n; j++) {
            if (base3[j][bit] != 2 || bit-1 < 0) row.push_back(openB ? -2 : -1);
            else row.push_back(i+1 + base3[j][bit-1]*8);
        }
        for (int &j : row) if (j >= 1+8+8+8) j = -2;
        ans.push_back(row);
    }
    return ans;
}

/*
tro pigra por komenti
*/

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