oj.uz

Submission #695788

# Submission time Handle Problem Language Result Execution time Memory
695788 2023-02-05T07:56:03 Z finn__ Flight to the Ford (BOI22_communication) C++17
70 / 100
 4174 ms 2008 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1824 KB Output is correct
2 Correct 185 ms 1940 KB Output is correct
3 Correct 205 ms 1748 KB Output is correct
4 Correct 109 ms 1748 KB Output is correct
5 Correct 148 ms 1684 KB Output is correct
6 Correct 439 ms 1828 KB Output is correct
7 Correct 931 ms 1816 KB Output is correct

Subtask #2
55.000015 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 844 ms 1884 KB Output is partially correct
2 Partially correct 511 ms 1716 KB Output is partially correct
3 Partially correct 588 ms 1664 KB Output is partially correct
4 Partially correct 1211 ms 1868 KB Output is partially correct
5 Partially correct 615 ms 1664 KB Output is partially correct
6 Partially correct 401 ms 1660 KB Output is partially correct
7 Partially correct 2481 ms 1948 KB Output is partially correct
8 Partially correct 4122 ms 1984 KB Output is partially correct
9 Partially correct 3819 ms 1800 KB Output is partially correct
10 Partially correct 3514 ms 2004 KB Output is partially correct
11 Partially correct 3631 ms 1960 KB Output is partially correct
12 Partially correct 3531 ms 1792 KB Output is partially correct
13 Partially correct 3881 ms 1812 KB Output is partially correct
14 Partially correct 3500 ms 2008 KB Output is partially correct
15 Partially correct 1694 ms 1756 KB Output is partially correct
16 Partially correct 4174 ms 1880 KB Output is partially correct
17 Partially correct 1057 ms 1752 KB Output is partially correct
18 Partially correct 1132 ms 1908 KB Output is partially correct
19 Partially correct 1137 ms 1840 KB Output is partially correct
20 Partially correct 1040 ms 1908 KB Output is partially correct
21 Partially correct 1148 ms 1756 KB Output is partially correct
22 Partially correct 1075 ms 1848 KB Output is partially correct
23 Partially correct 2053 ms 1772 KB Output is partially correct
24 Correct 135 ms 1712 KB Output is correct
25 Correct 103 ms 1780 KB Output is correct
26 Correct 231 ms 1720 KB Output is correct
27 Correct 135 ms 1692 KB Output is correct
28 Correct 206 ms 1884 KB Output is correct
29 Correct 377 ms 1736 KB Output is correct
30 Correct 821 ms 1800 KB Output is correct