Submission #753450

#	Time	Username	Problem	Language	Result	Execution time	Memory
753450		jakobrs	Flight to the Ford (BOI22_communication)	C++17	70 / 100	3449 ms	2036 KiB

communication

#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 / 15
• Subtask 2: 55.000015000000005 / 85