#include"communication.h"
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7;
int aux[] = {0b0000, 0b1001, 0b0110};
int get_bad(int x) {
vi ans;
for(int k = 0; k < 3; k++)
if(x == aux[k])
ans.PB(k);
for(int i = 0; i < 4; i++) {
int y = x ^ (1 << i);
for(int k = 0; k < 3; k++)
if(y == aux[k])
ans.PB(k);
for(int j = 0; j < i - 1; j++) {
int z = y ^ (1 << j);
for(int k = 0; k < 3; k++)
if(z == aux[k])
ans.PB(k);
}
}
for(int i = 0; i < 3; i++)
if(count(ALL(ans), i) == 0)
return i;
throw;
};
void encode(int n, int x) {
auto send_3 = [&] (int y) {
assert(0 <= y && y < 3);
int sent = 0;
for(int i = 0; i < 4; i++)
sent |= send(aux[y] >> i & 1) << i;
#ifdef CHEISSMART
assert(get_bad(sent) != y);
#endif
return get_bad(sent);
};
function<void(int)> go = [&] (int m) { // [0, m);
if(m < 3) {
send_3(x);
return;
}
int he = m / 3, be = he * 2;
// [0, he), [he, be), [be, m)
if(x < he) {
int bad = send_3(0);
if(bad == 1) go(he + m - be);
else if(bad == 2) go(be);
else throw;
} else if(x < be) {
int bad = send_3(1);
if(bad == 0) {
x -= he;
go(m - he);
} else if(bad == 2) {
go(be);
} else throw;
} else {
int bad = send_3(2);
if(bad == 0) {
x -= he;
go(m - he);
} else if(bad == 1) {
x -= be;
go(he + m - be);
} else throw;
}
};
go(n + 1);
}
pi decode(int n) {
auto get_3 = [&] () {
int x = 0;
for(int i = 0; i < 4; i++)
x |= receive() << i;
return get_bad(x);
};
function<pi(int)> go = [&] (int m) -> pi { // [0, m);
if(m < 3) {
int bad = get_3();
if(bad == 0) return {1, 2};
else if(bad == 1) return {0, 2};
else return {0, 1};
}
int he = m / 3, be = he * 2;
// [0, he), [he, be), [be, m)
int bad = get_3();
if(bad == 0) {
auto [x, y] = go(m - he);
x += he, y += he;
return {x, y};
} else if(bad == 1) {
auto [x, y] = go(he + m - be);
if(x >= he) x += be - he;
if(y >= he) y += be - he;
return {x, y};
} else {
auto [x, y] = go(be);
return {x, y};
}
};
return go(n + 1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
487 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
