Submission #695788

#	Time	Username	Problem	Language	Result	Execution time	Memory
695788		finn__	Flight to the Ford (BOI22_communication)	C++17	70 / 100	4174 ms	2008 KiB

communication

#include <bits/stdc++.h>
#include "communication.h"
using namespace std;

#define MAX_BITS 30

// 0 -> 0000, 1 -> 0110, 2 -> 1001, 3 -> 1111
int e[4] = {0, 6, 9, 15};
// The inverse of e including errors.
pair<int, int> d[16] = {{0, 2},  // 0000
                        {0, 2},  // 0001
                        {0, 1},  // 0010
                        {1, 2},  // 0011
                        {0, 1},  // 0100
                        {0, 3},  // 0101
                        {1, 3},  // 0110
                        {1, 3},  // 0111
                        {0, 2},  // 1000
                        {0, 2},  // 1001
                        {0, 3},  // 1010
                        {2, 3},  // 1011
                        {1, 2},  // 1100
                        {2, 3},  // 1101
                        {1, 3},  // 1110
                        {1, 3}}; // 1111

int bit_reverse(int N, int X)
{
    int Y = 0;
    for (int i = 0; i < N; i++)
        Y |= ((X >> i) & 1) << (N - i - 1);
    return Y;
}

// Sends exactly 4 * MAX_BITS bits to encode any message.
void encode(int N, int X)
{
    X = bit_reverse(MAX_BITS, X - 1); // Encode higher-order bits first.
    for (unsigned i = 0; i < MAX_BITS; i++)
    {
        int Y = e[X & 3], Z = 0;
        for (unsigned j = 0; j < 4; j++)
        {
            Z = (Z << 1) | send(Y & 1);
            Y >>= 1;
        }

        int K = (X >> 2) << 1;
        if (d[Z].second == (X & 3))
            K ^= 1;
        else
            assert(d[Z].first == (X & 3));
        X = K;
    }
}

pair<int, int> get_interval(pair<int, int> p, pair<int, int> q, int i)
{
    switch (i)
    {
    case 0:
        return {p.first, (p.first + p.second) / 2};
    case 1:
        return {q.first, (q.first + q.second) / 2};
    case 2:
        return {(p.first + p.second + 1) / 2, p.second};
    case 3:
        return {(q.first + q.second + 1) / 2, q.second};
    default:
        assert(0);
    }
}

std::pair<int, int> decode(int N)
{
    pair<int, int> p = {0, (1 << (MAX_BITS - 1)) - 1},
                   q = {1 << (MAX_BITS - 1), (1 << MAX_BITS) - 1};

    for (unsigned i = 0; i < MAX_BITS; i++)
    {
        int Y = 0;
        for (unsigned j = 0; j < 4; j++)
            Y = (Y << 1) | receive();

        pair<int, int> r = get_interval(p, q, d[Y].first);
        q = get_interval(p, q, d[Y].second);
        p = r;
    }

    assert(p.first == p.second);
    assert(q.first == q.second);

    if (p.first + 1 > N)
        p.first = q.first;
    else if (q.first + 1 > N)
        q.first = p.first;

    return {p.first + 1, q.first + 1};
}

• Subtask 1: 15 / 15
• Subtask 2: 55.000015000000005 / 85