Submission #752730

#	Time	Username	Problem	Language	Result	Execution time	Memory
752730		jakobrs	Flight to the Ford (BOI22_communication)	C++17	68 / 100	4994 ms	2848 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};

// 252, 149, 8, 104, 154
// ['11111100', '10010101', '00001000', '01101000', '10011010']
constexpr const int STRINGS[5][8] = {
    {1, 1, 1, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 1},
    {0, 0, 0, 0, 1, 0, 0, 0}, {0, 1, 1, 0, 1, 0, 0, 0},
    {1, 0, 0, 1, 1, 0, 1, 0},
};
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 <= 5) {
        for (i64 i = 0; i < 8; i++) {
            send(STRINGS[x][i]);
        }
    } else {
        i64 error = 0;

        for (i64 i = 0; 1 << i < n; i++) {
            int value = x & (1 << i) ? 1 : 0;
            std::cerr << value << '\n';
            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;
}

std::pair<int, int> decode(int n) {
    if (n <= 5) {
        i64 read = 0;
        for (i64 i = 0; i < 8; i++) {
            read |= receive() << (7 - i);
        }
        auto [x, y] = STRINGS_BACKWARDS[read];
        std::cerr << x << ' ' << y << '\n';
        return {x + 1, std::min(y + 1, 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: 52.999965 / 85