oj.uz

Submission #753450

# Submission time Handle Problem Language Result Execution time Memory
753450 2023-06-05T08:37:26 Z jakobrs Flight to the Ford (BOI22_communication) C++17
70 / 100
 3449 ms 2036 KB 
#include <array>
#include <iostream>

using i64 = int64_t;

int send(int s);
int receive();

constexpr const i64 FIB[32] = {
    1,      2,      3,      5,      8,      13,      21,      34,
    55,     89,     144,    233,    377,    610,     987,     1597,
    2584,   4181,   6765,   10946,  17711,  28657,   46368,   75025,
    121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578};

constexpr const i64 STRINGS[8] = {
    0, 30, 199, 217, 289, 319, 486, 504,
};

constexpr const std::pair<int, int> STRINGS_BACKWARDS[256] = {
    {1, 2}, {1, 2}, {2, 0}, {0, 1}, {1, 0}, {1, 0}, {0, 1}, {1, 0}, {2, 4},
    {2, 0}, {2, 4}, {4, 0}, {2, 0}, {2, 0}, {4, 0}, {4, 0}, {1, 4}, {1, 0},
    {4, 0}, {4, 0}, {1, 0}, {1, 0}, {0, 1}, {1, 0}, {2, 4}, {2, 0}, {2, 4},
    {4, 0}, {1, 2}, {1, 2}, {4, 0}, {1, 4}, {2, 3}, {2, 3}, {2, 3}, {0, 1},
    {0, 1}, {0, 1}, {0, 1}, {0, 1}, {2, 3}, {2, 3}, {2, 3}, {0, 1}, {2, 3},
    {2, 3}, {0, 1}, {0, 1}, {1, 4}, {1, 0}, {4, 0}, {4, 0}, {1, 0}, {1, 0},
    {0, 1}, {1, 0}, {3, 4}, {3, 0}, {3, 4}, {4, 0}, {1, 3}, {1, 3}, {4, 0},
    {1, 4}, {2, 3}, {2, 3}, {2, 3}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1},
    {2, 3}, {2, 3}, {2, 3}, {0, 1}, {2, 3}, {2, 3}, {0, 1}, {0, 1}, {0, 1},
    {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 2}, {0, 2},
    {2, 0}, {0, 1}, {0, 2}, {0, 2}, {0, 1}, {0, 1}, {3, 0}, {3, 0}, {3, 0},
    {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 3}, {0, 3}, {3, 0}, {0, 1},
    {0, 3}, {0, 3}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1},
    {0, 1}, {0, 1}, {0, 1}, {0, 3}, {0, 3}, {3, 0}, {0, 1}, {0, 3}, {0, 3},
    {0, 1}, {0, 1}, {1, 2}, {1, 2}, {2, 0}, {0, 1}, {1, 0}, {1, 0}, {0, 1},
    {1, 0}, {2, 4}, {2, 0}, {2, 4}, {4, 0}, {2, 0}, {2, 0}, {4, 0}, {4, 0},
    {1, 4}, {1, 0}, {4, 0}, {4, 0}, {1, 0}, {1, 0}, {0, 1}, {1, 0}, {2, 4},
    {2, 0}, {2, 4}, {4, 0}, {1, 2}, {1, 2}, {4, 0}, {1, 4}, {2, 0}, {2, 0},
    {2, 0}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 2}, {0, 2}, {2, 0},
    {0, 1}, {0, 2}, {0, 2}, {0, 1}, {0, 1}, {1, 4}, {1, 0}, {4, 0}, {4, 0},
    {0, 1}, {0, 1}, {0, 1}, {1, 0}, {0, 4}, {0, 1}, {4, 0}, {4, 0}, {0, 1},
    {0, 1}, {0, 4}, {1, 4}, {1, 3}, {1, 3}, {3, 0}, {0, 1}, {1, 0}, {1, 0},
    {0, 1}, {1, 0}, {3, 4}, {3, 0}, {3, 4}, {4, 0}, {3, 0}, {3, 0}, {4, 0},
    {4, 0}, {1, 4}, {1, 0}, {4, 0}, {4, 0}, {0, 1}, {0, 1}, {0, 1}, {1, 0},
    {0, 4}, {0, 1}, {4, 0}, {4, 0}, {0, 1}, {0, 1}, {0, 4}, {1, 4}, {3, 0},
    {3, 0}, {3, 0}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 3}, {0, 3},
    {3, 0}, {0, 1}, {0, 3}, {0, 3}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1},
    {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 3}, {0, 3}, {3, 0}, {0, 1},
    {0, 3}, {0, 3}, {0, 1}, {0, 1}};

void encode(int n, int x) {
    x -= 1;
    if (n <= 8) {
        for (i64 i = 0; i < 9; i++) {
            send(!!(STRINGS[x] & (1 << i)));
        }
    } else {
        i64 error = 0;

        for (i64 i = 0; 1 << i < n; i++) {
            int value = x & (1 << i) ? 1 : 0;
            if (send(value) != value) {
                error += FIB[i];
            }
        }

        i64 bits = 0;
        while (1 << bits < n) bits += 1;

        encode(FIB[bits], error + 1);
    }
}

int decompress(int n) {
    int result = 0;

    for (i64 i = 31; i >= 0; i--) {
        if (n >= FIB[i]) {
            n -= FIB[i];
            result |= 1 << i;
        }
    }

    return result;
}

bool is_valid(i64 x) {
    return (x & (x >> 1)) == 0;
}

std::pair<int, int> decode(int n) {
    if (n <= 8) {
        i64 read = 0;
        for (i64 i = 0; i < 9; i++) {
            read |= receive() << i;
        }

        // this is kinda cursed
        i64 res[2] {0, 0};
        i64 *ptr = &res[0];
        for (i64 i = 0; i < 8; i++) {
            if (is_valid(read ^ STRINGS[i])) {
                *(ptr++) = i;
            }
        }

        return {std::min(res[0] + 1, (i64)n), std::min(res[1] + 1, (i64)n)};
    } else {
        int message = 0;

        for (i64 i = 0; 1 << i < n; i++) {
            message |= receive() << i;
        }

        i64 bits = 0;
        while (1 << bits < n) bits += 1;

        auto [corr1, corr2] = decode(FIB[bits]);
        auto [x, y] = std::array<int, 2>{message ^ decompress(corr1 - 1),
                                         message ^ decompress(corr2 - 1)};

        return {std::min(x + 1, n), std::min(y + 1, n)};
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1760 KB Output is correct
2 Correct 17 ms 1620 KB Output is correct
3 Correct 24 ms 1668 KB Output is correct
4 Correct 17 ms 1664 KB Output is correct
5 Correct 22 ms 1824 KB Output is correct
6 Correct 39 ms 1864 KB Output is correct
7 Correct 65 ms 1688 KB Output is correct

Subtask #2
55.000015 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 853 ms 1772 KB Output is partially correct
2 Partially correct 486 ms 1716 KB Output is partially correct
3 Partially correct 508 ms 1668 KB Output is partially correct
4 Partially correct 760 ms 1664 KB Output is partially correct
5 Partially correct 809 ms 1684 KB Output is partially correct
6 Partially correct 663 ms 1700 KB Output is partially correct
7 Partially correct 2314 ms 1972 KB Output is partially correct
8 Partially correct 3449 ms 2036 KB Output is partially correct
9 Partially correct 3111 ms 1924 KB Output is partially correct
10 Partially correct 2873 ms 1864 KB Output is partially correct
11 Partially correct 3082 ms 1892 KB Output is partially correct
12 Partially correct 3184 ms 1792 KB Output is partially correct
13 Partially correct 2924 ms 1884 KB Output is partially correct
14 Partially correct 2969 ms 1940 KB Output is partially correct
15 Partially correct 1585 ms 1728 KB Output is partially correct
16 Partially correct 3078 ms 1788 KB Output is partially correct
17 Partially correct 852 ms 1748 KB Output is partially correct
18 Partially correct 913 ms 1728 KB Output is partially correct
19 Partially correct 1038 ms 1796 KB Output is partially correct
20 Partially correct 912 ms 1876 KB Output is partially correct
21 Partially correct 973 ms 1736 KB Output is partially correct
22 Partially correct 971 ms 1908 KB Output is partially correct
23 Partially correct 1541 ms 1736 KB Output is partially correct
24 Correct 10 ms 1668 KB Output is correct
25 Correct 20 ms 1696 KB Output is correct
26 Correct 27 ms 1676 KB Output is correct
27 Correct 10 ms 1688 KB Output is correct
28 Correct 21 ms 1608 KB Output is correct
29 Correct 43 ms 1808 KB Output is correct
30 Correct 74 ms 1600 KB Output is correct