oj.uz

Submission #626943

# Submission time Handle Problem Language Result Execution time Memory
626943 2022-08-12T02:33:09 Z I_love_Hoang_Yen Prisoner Challenge (IOI22_prison) C++17
90 / 100
 14 ms 980 KB 
#include "bits/stdc++.h"
using namespace std;
 
int p3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};
 
// base 3
int get_bit(int n, int bit) {
    return (n % p3[bit + 1]) / p3[bit];
}
 
const int NBIT = 8;  // 3**8 > 5000

int encode(int b, int t) {
    if (b < 0) return 0;
    return 1 + (NBIT - b - 1) * 3 + t;
}
 
std::vector<std::vector<int>> devise_strategy(int n) {
    const int NSTATE = 22;
    std::vector<std::vector<int>> res(NSTATE, std::vector<int> (n+1, 0));

    // 0
    {
        res[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            int t = get_bit(i, NBIT - 1);
            res[0][i] = encode(NBIT - 1, t);
        }
    }

    // compare each digit in base 3
    for (int bit = NBIT - 1; bit >= 1; --bit) {
        for (int t = 0; t < 3; ++t) {
            int state = encode(bit, t);

            // 7 -> read 1
            // 6 -> read 0
            int cur = bit % 2;
            int last = 1 - cur;

            res[state][0] = cur;

            for (int i = 1; i <= n; ++i) {
                int cur_bit = get_bit(i, bit);
                if (t < cur_bit) res[state][i] = -1 - last;
                else if (t > cur_bit) res[state][i] = -1 - cur;
                else {
                    // 2 digits are equal -> we continue to next digit
                    // to improve, we read next digit of current number and store it directly
                    // (alternating 2 numbers)
                    if (bit > 2) res[state][i] = encode(bit - 1, get_bit(i, bit - 1));
                    else {
                        // for last 2 digits, manual casework
                        int r = i % 9;
                        if (r == 0) res[state][i] = -1 - cur;
                        else if (r == 8) res[state][i] = -1 - last;
                        else if (r <= 4) res[state][i] = 19;  // 1 2 3 4
                        else res[state][i] = 20;              // 5 6 7
                    }
                }
            }
        }
    }

    // 19, 20
    for (int state : {19, 20}) {
        int cur = 1, last = 0;
        res[state][0] = cur;

        for (int i = 1; i <= n; ++i) {
            // last 2 digits
            int r = i % 9;
            if (r == 0) res[state][i] = -1 - cur;
            else if (r == 8) res[state][i] = -1 - last;
            else if (state == 19) {
                if (r == 1) res[state][i] = -1 - cur;
                else if (r >= 4) res[state][i] = -1 - last;
                else res[state][i] = 21;
            } else {
                // state == 20
                if (r <= 5) res[state][i] = -1 - cur;
                else if (r == 7) res[state][i] = -1 - last;
                else res[state][i] = 21;
            }
        }
    }

    // 21
    {
        int cur = 0, last = 1;
        res[21][0] = cur;

        for (int i = 1; i <= n; ++i) {
            int r = i % 9;
            if (r <= 4) {
                if (r <= 2) res[21][i] = -1 - cur;
                else res[21][i] = -1 - last;
            } else {
                if (r <= 6) res[21][i] = -1 - cur;
                else res[21][i] = -1 - last;
            }
        }
    }
 
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
80.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 0 ms 212 KB Output is partially correct
3 Partially correct 0 ms 212 KB Output is partially correct
4 Partially correct 6 ms 596 KB Output is partially correct
5 Partially correct 14 ms 804 KB Output is partially correct
6 Partially correct 12 ms 956 KB Output is partially correct
7 Partially correct 11 ms 980 KB Output is partially correct
8 Partially correct 0 ms 212 KB Output is partially correct
9 Partially correct 1 ms 340 KB Output is partially correct
10 Partially correct 2 ms 340 KB Output is partially correct
11 Partially correct 5 ms 552 KB Output is partially correct
12 Partially correct 9 ms 852 KB Output is partially correct