Submission #1084126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084126		SamueleVid	Prisoner Challenge (IOI22_prison)	C++17	30 / 100	19 ms	2140 KiB

prison

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> devise_strategy(int N) {
    int digits = log2(N) + 1;
    // xxxxxx y z
    // x = quale cifra sto guardando, sapendo che quelle più alte sono uguali
    // y = se quella cifra compare o no nel numero in binario
    // z = a quale bag si riferisce la cifra. 0 : A, 1 : B

    vector<vector<int>> s(4 * (digits + 1), vector<int>(N + 1));

    for (int x = 0; x < 4 * (digits + 1); x ++) {
        int who = x & 1;
        int bit = (bool)(x & 2);
        int digit = (x >> 2);
        // cout << "x : " << x << '\n';
        // cout << "who, bit, digit " << who << " " << bit << " " << digit << '\n';
        if (digit == 0) {
            // start, occupa quattro casi ma è solo uno tho
            s[x][0] = 0;
            int who_next = 0;
            int digit_next = digits;
            for (int j = 1; j <= N; j ++) {
                int bit_next = (bool)(j & (1 << (digit_next - 1)));
                s[x][j] = (digit_next << 2) + (bit_next << 1) + who_next;
            }
            continue;
        }
        if (who == 0) {
            s[x][0] = 1;
            int who_next = 1;
            int digit_next = digit;
            for (int j = 1; j <= N; j ++) {
                int bit_next = (bool)(j & (1 << (digit_next - 1)));
                // cout << "bit_next : " << bit_next << '\n';
                if (bit_next < bit) s[x][j] = -2;
                if (bit < bit_next) s[x][j] = -1;
                if (bit == bit_next) s[x][j] = (digit_next << 2) + (bit_next << 1) + who_next;
            }
        }

        if (who == 1) {
            s[x][0] = 0;
            int who_next = 0;
            int digit_next = digit - 1;
            for (int j = 1; j <= N; j ++) {
                int bit_next = (bool)(j & (1 << (digit_next - 1)));
                s[x][j] = (digit_next << 2) + (bit_next << 1) + who_next;
            }
        }
    }
    
    return s;
}

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