#include <bits/stdc++.h>
#include "communication.h"
using namespace std;
// 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;
}
void encode(int N, int X) // Sends exactly 120 bits to encode any message.
{
X = bit_reverse(30, X - 1); // Encode higher-order bits first.
for (unsigned i = 0; i < 30; i++)
{
int Y = e[X & 3], Z = 0;
for (unsigned j = 0; j < 4; j++)
Z = (Z << 1) | send(Y & 1), Y >>= 1;
Z = bit_reverse(4, Z);
X >>= 2;
X = (X << 1) | (int)(d[Z].second == e[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 << 29}, q = {1 << 29, 1 << 30};
for (unsigned i = 0; i < 30; i++)
{
int Y = 0;
for (unsigned j = 0; j < 4; j++)
Y = (Y << 1) | receive();
Y = bit_reverse(4, Y);
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};
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
389 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
