#include"communication.h"
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
struct segment
{
int l, r;
};
int siz(const vector<segment>& v)
{
int sum = 0;
for (segment i : v) sum += i.r - i.l + 1;
return sum;
}
int kth(const vector<segment> &v, int k) // k-ty prvok ktory mame (1-indexovane)
{
for (segment i : v)
{
if (i.l + k - 1 <= i.r) return i.l + k - 1;
k -= (i.r - i.l + 1);
}
}
vector<segment> excl(const vector<segment>& v, int l, int r) // vynechaj prvky l az r
{
vector<segment> nw;
for (segment i : v)
{
if (i.l <= l - 1) nw.push_back({ i.l, min(i.r, l - 1) });
if (i.r >= r + 1) nw.push_back({ max(i.l, r + 1), i.r });
}
return nw;
}
vector<segment> skip(const vector<segment>& v, vector<int> s, int a0, int a1)
{
int num = a0 * 2 + a1, l = 1, r = 0;
for (int i = 0; i < num; i++) l += s[i];
for (int i = 0; i <= num; i++) r += s[i];
return excl(v, kth(v, l), kth(v, r));
}
void encode(int n, int x)
{
vector<segment> v = { {1,n} };
while (true)
{
int S = siz(v);
if (S < 4) break;
vector<int> s(4, 0);
for (int i = 0; i < 4; i++) s[i] = S / 4 + (i < S % 4);
// opytame sa na [0, 1] a [0, 2]
int pos = 0, sum = 0;
for (int i = 0; i < 4; i++)
{
sum += s[i];
if (kth(v, sum) < x) pos++;
}
int a0, a1;
a0 = send(pos >> 1);
a1 = send(pos & 1);
v = skip(v, s, a0 ^ 1, a1 ^ 1);
}
int S = siz(v);
if (S < 3) return;
int sent = -1;
if (kth(v, 1) == x) sent = send(1);
else sent = send(0);
if (sent == 0)
{
int sent = -1;
if (kth(v, 1) == x) sent = send(1);
else sent = send(0);
if (sent == 1) send(kth(v, 2) == x);
}
else send(kth(v, 2) == x);
}
pair<int, int> decode(int n)
{
vector<segment> v = { {1,n} };
while (true)
{
int S = siz(v);
if (S < 4) break;
vector<int> s(4, 0);
for (int i = 0; i < 4; i++) s[i] = S / 4 + (i < S % 4);
// opytame sa na [0, 1] a [0, 2]
int a0 = receive(), a1 = receive();
v = skip(v, s, a0 ^ 1, a1 ^ 1);
}
vector<int> p = { kth(v,1), kth(v,2), kth(v,3) };
if (receive()) return receive() ? make_pair(p[0], p[1]) : make_pair(p[0], p[2]);
if (receive()) return receive() ? make_pair(p[0], p[1]) : make_pair(p[0], p[2]);
else return make_pair(p[1], p[2]);
}
