oj.uz

답안 #695281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
695281 2023-02-04T22:07:47 Z finn__ Flight to the Ford (BOI22_communication) C++17
0 / 100
 70 ms 212 KB 
#include <bits/stdc++.h>
#include "communication.h"
using namespace std;

#define MAX_BITS 4

// 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[bit_reverse(2, X) & 3], Z = 0;
        for (unsigned j = 0; j < 4; j++)
            Z = (Z << 1) | send(Y & 1), Y >>= 1;

        X = ((X >> 2) << 1) | (int)(d[Z].second == e[bit_reverse(2, X) & 3]);
    }
}

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 {(p.first + p.second) / 2, p.second};
    case 2:
        return {q.first, (q.first + q.second) / 2};
    case 3:
        return {(q.first + q.second) / 2, q.second};
    default:
        assert(0);
    }
}

std::pair<int, int> decode(int N)
{
    pair<int, int> p = {0, 1 << (MAX_BITS - 1)},
                   q = {1 << (MAX_BITS - 1), 1 << MAX_BITS};
    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;
    }
    return {p.first + 1, q.first + 1};
}

Subtask #1
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 212 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 204 KB Not correct
2 Halted 0 ms 0 KB -