#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, 0b1111};
vi get_bad(int x) {
vi ans;
for(int k = 0; k < 4; 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 < 4; 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 < 4; k++)
if(z == aux[k])
ans.PB(k);
}
}
vi bad;
for(int i = 0; i < 4; i++)
if(count(ALL(ans), i) == 0)
bad.PB(i);
return bad;
};
void encode(int n, int x) {
x--;
auto send_4 = [&] (int y) {
assert(0 <= y && y < 4);
int sent = 0;
for(int i = 0; i < 4; i++)
sent |= send(aux[y] >> i & 1) << i;
return get_bad(sent);
};
function<void(int)> go = [&] (int m) { // [0, m);
assert(x < m);
if(m <= 4) {
send_4(x);
return;
}
int b = m / 2, a = b / 2, c = (b + m) / 2;
int aux[] = {0, a, b, c, m};
int which = 0;
while(!(aux[which] <= x && x < aux[which + 1]))
which++;
vi bad = send_4(which);
int new_m = m, new_x = x;
for(int i = 0; i < 4; i++) {
if(count(ALL(bad), i)) {
new_m -= aux[i + 1] - aux[i];
if(aux[i] < x) new_x -= aux[i + 1] - aux[i];
}
}
x = new_x;
go(new_m);
};
go(n);
}
pi decode(int n) {
auto get_4 = [&] () {
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 <= 4) {
vi bad = get_4(), good;
for(int i = 0; i < 4; i++)
if(count(ALL(bad), i) == 0)
good.PB(i);
while(SZ(good) < 2)
good.PB(0);
return {good[0], good[1]};
}
vi bad = get_4();
int b = m / 2, a = b / 2, c = (b + m) / 2;
int aux[] = {0, a, b, c, m}, new_m = m;
for(int i = 0; i < 4; i++) {
if(count(ALL(bad), i)) {
new_m -= aux[i + 1] - aux[i];
}
}
auto go_back = [&] (int x) -> int {
for(int i = 0; i < 4; i++) {
if(count(ALL(bad), i)) {
x += aux[i + 1] - aux[i];
} else {
if(aux[i] <= x && x < aux[i + 1])
return x;
}
}
throw;
};
auto[x, y] = go(new_m);
return {go_back(x), go_back(y)};
};
auto[x, y] = go(n);
return {x + 1, y + 1};
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
481 ms |
200 KB |
Security violation! |
| 2 |
Halted |
0 ms |
0 KB |
- |
