Submission #1070553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070553		c2zi6	Prisoner Challenge (IOI22_prison)	C++17	30 / 100	38 ms	3152 KiB

prison

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "prison.h"

int n;
VVI ans;

map<VI, int> encode;
map<int, VI> decode;
// ind, type, val

int STARTBIT = 12;

void prisoner(int x, int y) {
    if (!decode.count(x)) return;
    VI vec = decode[x];

    int type;
    if (x == 0) type = 0;
    else type = vec[1];

    if (type) {
        /* Es gitem A-i bit@, hamematenq B-i biti het*/
        ans[x][0] = 1;

        int ind = vec[0];
        int valA = vec[2];
        int valB = bool(y & (1<<ind));
        if (valA < valB) ans[x][y] = -1;
        else if (valB < valA) ans[x][y] = -2;
        else {
            ind--;
            if (ind < 0) return;
            VI write;
            write.pb(ind);
            write.pb(0);
            write.pb(valB);
            ans[x][y] = encode[write];
        }
    } else {
        /* Es chitem A-i bit@, A-i bit@ grenq */
        ans[x][0] = 0;

        int ind;
        if (x == 0) ind = STARTBIT;
        else ind = vec[0];
        int val = bool(y & (1<<ind));
        VI write;
        write.pb(ind);
        write.pb(1);
        write.pb(val);
        ans[x][y] = encode[write];
    }
}

VVI devise_strategy(int N) {n = N;
    decode[0] = {STARTBIT, 0, 0};
    encode[{STARTBIT, 0, 0}] = 0;
    
    int id = 1;
    replr(ind, 0, STARTBIT) replr(type, 0, 1) replr(val, 0, 1) {
        VI vec = {ind, type, val};
        if (vec == decode[0]) continue;
        encode[vec] = id;
        decode[id] = vec;
        id++;
    }

    /*rep(i, id) {*/
    /*    cout << i << ": ";*/
    /*    VI vec = decode[i];*/
    /*    cout << vec[0] << " " << vec[1] << " " << vec[2] << endl;*/
    /*}*/

    int B = id;
    ans = VVI(B, VI(n+1));
    replr(x, 0, B-1) {
        replr(y, 1, n) {
            prisoner(x, y);
        }
    }


    return ans;


    while (true) {
        int A, B;
        cin >> A >> B;
        int cur = 0;
        rep(i, 20) {
            VI vec = decode[cur];
            cout << "Grataxtakin grac e " << cur << ", aysinqn.." << endl;
            if (vec[1]) {
                cout << "es gitem or A-i " << vec[0] << "-rd bit@ " << vec[2] << " e" << endl;
            } else {
                cout << "es chitem A-i masin hech ban, bayc hasel em " << vec[0] << "-rd bit" << endl;
            }

            cout << "Kbace " << (ans[cur][0] ? "B" : "A") << " u ";
            int val = (ans[cur][0] ? B : A);
            cout << "ktesni " << val << endl;
            if (ans[cur][val] == -1) {
                cout << "PATASXAN@ A" << endl;
                goto verj;
            }
            if (ans[cur][val] == -2) {
                cout << "PATASXAN@ B" << endl;
                goto verj;
            }
            cout << endl;

            cur = ans[cur][val];
        }
verj:;
    }
    /*rep(i, B) {*/
    /*    rep(j, n+1) {*/
    /*        cout << ans[i][j] << " ";*/
    /*    }*/
    /*    cout << endl;*/
    /*}*/

    return ans;
}

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