Submission #1018200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018200		ProtonDecay314	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	8 ms	1116 KiB

prison

/* AM+DG */

/*
AB
A or X, depending on the last query's result

2 queries to get letter 1

Then N - 2 queries for everything except the last letter

Then 2 queries for the last letter

AZXAZYBAZYXAZYY

1-3 inspect B
4-6 ins A
7-9 ins B
10-12 ins A
13-15 ins B
16-18 ins A
19-21 ins B
22 ins A
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

// #define DEBUG

vvi devise_strategy(int N) {
    const int CHOOSE_A = 0, CHOOSE_B = 1;
    const int GUESS_A = -1, GUESS_B = -2;
    vvi s;
    for(int i = 0; i <= 22; i++) {
        vi sr(N + 1, 0);
        s.pb(sr);
    }

    vi p3 = {1, 3, 9, 27, 81, 243, 729, 2187}; 
    // x = 0

    s[0][0] = CHOOSE_A; // Initially inspect bag A

    LI(j, 1, N + 1) {
        s[0][j] = (j / p3[7]) + 1;
    }

    // Do the normal ones first
    LI(x, 1, 22) {
        int act_num = x - 1;
        int trigit_pos = 7 - act_num / 3;
        int prev_trigit_value = act_num % 3;
        int cur_bag = s[x][0] = (((act_num / 3) & 0b1) ? CHOOSE_A : CHOOSE_B);
        // cout << trigit_pos << endl;
        LI(j, 1, N + 1) {
            int cur_val_at_trigit = (j / p3[trigit_pos]) % 3;

            if(cur_val_at_trigit < prev_trigit_value) {
                s[x][j] = (cur_bag == CHOOSE_A ? GUESS_A : GUESS_B);
            } else if(cur_val_at_trigit == prev_trigit_value) {
                if(trigit_pos - 1 > 0) {
                    // Business as usual! :D
                    s[x][j] = ((j / p3[trigit_pos - 1]) % 3) + 3 * (act_num / 3 + 1) + 1;
                } else {
                    // it's time for const-opt LOL
                    int cur_ones_trigit = (j / p3[trigit_pos - 1]) % 3;

                    if(cur_ones_trigit == 0) s[x][j] = (cur_bag == CHOOSE_A ? GUESS_A : GUESS_B);
                    else if(cur_ones_trigit == 2) s[x][j] = (cur_bag == CHOOSE_A ? GUESS_B : GUESS_A);
                    else s[x][j] = 22; // Special case
                }
            } else {
                s[x][j] = (cur_bag == CHOOSE_A ? GUESS_B : GUESS_A);
            }
        }
    }

    s[22][0] = CHOOSE_A;
    LI(j, 1, N + 1) {
        int cur_a_ones_val = j % 3;

        if(cur_a_ones_val == 0) s[22][j] = GUESS_A;
        if(cur_a_ones_val == 2) s[22][j] = GUESS_B;
        if(cur_a_ones_val == 1) s[22][j] = GUESS_B; // Doesn't matter, will never be reached
    }

    return s;
}

#ifdef DEBUG
int main() {
    int N;
    cin >> N;
    vvi s = devise_strategy(N);

    LI(x, 0, 23) {
        cout << x << " " << s[x][0] << endl;
    }

    return 0;
}
#endif

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