oj.uz

Submission #1084136

# Submission time Handle Problem Language Result Execution time Memory
1084136 2024-09-05T10:25:27 Z SamueleVid Prisoner Challenge (IOI22_prison) C++17
37 / 100
 13 ms 1368 KB 
#include <bits/stdc++.h>
using namespace std;

int BASE = 3;

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;
    // 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 + 1) * (digits + 1) - BASE, vector<int>(N + 1));

    for (int x = 0; x < (BASE + 1) * (digits + 1) - BASE; x ++) {
        int real_x = x + BASE;

        int bit = real_x % (BASE + 1);
        int digit = real_x / (BASE + 1);
        // cout << "--- x, real_x : " << x <<  " " << real_x << '\n';
        // cout << "who, bit, digit " << who << " " << bit << " " << digit << '\n';
        if (x == 0) {
            // start, occupa un po' di casi ma è solo uno tho
            s[x][0] = 0;
            int digit_next = digits;
            for (int j = 1; j <= N; j ++) {
                int bit_next = get_bit(j, digit_next - 1);
                s[x][j] = (digit_next * (BASE + 1)) + bit_next - BASE;
                // cout << "orig : " << (digit_next * (BASE + 1)) + bit_next << '\n';
                // cout << s[x][j] << '\n';
            }
            continue;
        }
        if (bit < BASE) {
            // cout << "CASO DIGIT" << '\n';
            s[x][0] = 1;
            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] = -2;
                if (bit < bit_next) s[x][j] = -1;
                if (bit == bit_next && digit_next > 1) { // in teoria non ci arriva, ma non potrebbe
                    // cout << "orig : " << (digit_next * (BASE + 1)) + BASE << '\n';
                    s[x][j] = (digit_next * (BASE + 1)) + BASE - BASE;
                }
                // cout << s[x][j] << '\n';
            }
        }
        if (bit == BASE) { 
            // cout << "CASO BASE" << '\n';
            s[x][0] = 0;
            int digit_next = digit - 1;
            if (digit_next == 0) continue; // finito le digits da controllare :/
            for (int j = 1; j <= N; j ++) {
                int bit_next = get_bit(j, digit_next - 1);
                s[x][j] = (digit_next * (BASE + 1)) + bit_next - BASE;
                // cout << "orig : " << (digit_next * (BASE + 1)) + bit_next << '\n';
                // cout << s[x][j] << '\n';
            }
        }
    }
    
    return s;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Strategy failed for N=243, A=1, B=243
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB Strategy failed for N=243, A=1, B=243
4 Halted 0 ms 0 KB -

Subtask #3
37.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Partially correct 5 ms 860 KB Output is partially correct
5 Partially correct 10 ms 1116 KB Output is partially correct
6 Partially correct 13 ms 1356 KB Output is partially correct
7 Partially correct 12 ms 1368 KB Output is partially correct
8 Correct 0 ms 348 KB Output is correct
9 Partially correct 1 ms 348 KB Output is partially correct
10 Partially correct 1 ms 348 KB Output is partially correct
11 Partially correct 5 ms 760 KB Output is partially correct
12 Partially correct 10 ms 1204 KB Output is partially correct