#include <bits/stdc++.h>
#include "communication.h"
using namespace std;
#define MAX_BITS 29
// 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;
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},
q = {1 << MAX_BITS, (1 << (MAX_BITS + 1)) - 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;
}
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};
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
256 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
342 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
