Submission #1085036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085036		SamueleVid	Prisoner Challenge (IOI22_prison)	C++17	70 / 100	10 ms	1196 KiB

prison

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

int BASE = 3;
int SHIFT = (BASE - 1) + (BASE - 1);

int get_bit(int num, int digit) {
    for (int i = 0; i < digit; i ++) {
        num /= BASE;
    }
    return num % BASE;
}

vector<vector<int>> devise_strategy(int N) {
    int digits = log(N) / log(BASE) + 1;
    // VVV questo ma con base diversa da 2 per minimizzare X
    // 3 * xxxxxx + y
    // x = quale cifra sto guardando, sapendo che quelle più alte sono uguali
    // y =  0 : sono in B e il bit di A è 0
    //      1 : sono in B e il bit di A è 1
    //      2 : sono in A e devo passare il bit di A in B

    vector<vector<int>> s((BASE) * (digits + 1) - SHIFT, vector<int>(N + 1));
    // shifta tutto di (B - 1) perché con digit == 0 c'è un solo caso (l'inizio), così risparmi numeri.
    // also guardando l'ultima cifra, se è 2 è peffo più alta, se 0 più bassa, solo se è 1 ha senso pushare

    for (int x = 0; x < (BASE) * (digits + 1) - SHIFT; x ++) {
        int real_x = x + SHIFT;
        // cout << "x , real_x -> " << x << " " << real_x << '\n'; 

        int bit = real_x % BASE;
        int digit = real_x / BASE;
        if (digit == 1) bit = 1;

        // cout << "bit, digit -> " << bit << " " << digit << '\n';
        if (x == 0) {
            // start, occupa un po' di casi ma è solo uno tho
            int digit_next = digits;
            s[x][0] = (digits + 1) % 2;
            // // cout << "seleziono " << (digits + 1) % 2 << '\n';

            // cout << "digits_next : " << digit_next << '\n';

            for (int j = 1; j <= N; j ++) {
                int bit_next = get_bit(j, digit_next - 1);
                // cout << "j, bit_next : " << j << " " << bit_next << '\n';
                if (digit_next == 1) {
                    // funziona con base 3
                    if (bit_next == 0) s[x][j] = -1;
                    else if (bit_next == 2) s[x][j] = -2;
                    else s[x][j] = 1;
                }
                else s[x][j] = (digit_next * BASE) + bit_next - SHIFT;

                // cout << s[x][j] << '\n';
            }
            continue;
        }
        // // cout << "CASO DIGIT" << '\n';
        s[x][0] = (digit % 2);
        // // cout << "seleziono " << (digit % 2) << '\n';
        int digit_next = digit;
        // // cout << "digit_next -> " << digit_next << '\n'; 
        for (int j = 1; j <= N; j ++) {
            int bit_next = get_bit(j, digit_next - 1);
            // // cout << "bit_next : " << bit_next << '\n';
            if (bit_next < bit) s[x][j] = (digit % 2) ? -2 : -1;
            if (bit < bit_next) s[x][j] = (digit % 2) ? -1 : -2;
        }

        digit_next -= 1;
        if (digit_next == 0) continue;

        // cout << "digit_next : " << digit_next << '\n';

        for (int j = 1; j <= N; j ++) {
            int bit_next = get_bit(j, digit_next - 1);
            // cout << "j, bit_next : " << j << " " << bit_next << '\n';
            if (digit_next == 1 && s[x][j] != -1 && s[x][j] != -2) { // && s[x][j] != -1 && s[x][j] != -2
                // // cout << "vado dentro " << '\n';
                // funziona con base 3
                if (bit_next == 0) s[x][j] = ((digit) % 2) ? -2 : -1;
                if (bit_next == 2) s[x][j] = ((digit) % 2) ? -1 : -2;
                if (bit_next == 1) s[x][j] = 1;
            }
            if (digit_next > 1 && s[x][j] != -1 && s[x][j] != -2) {
                s[x][j] = (digit_next * BASE) + bit_next - SHIFT;
            }
            // cout << s[x][j] << '\n';
        }
    }

    // for (int x = 0; x < s.size(); x ++) {
    //     cout << x << " : ";
    //     for (int j = 1; j <= N; j ++) cout << s[x][j] << " ";
    //     cout << '\n';
    // }
    
    return s;
}

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