#include "communication.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> merge_vec(vector<pair<int, int>> x, vector<pair<int, int>> y) {
int sz_x = x.size();
int sz_y = y.size();
int i = 0, j = 0;
vector<pair<int, int>> res;
while (i < sz_x || j < sz_y) {
if (j == sz_y || (i < sz_x && x[i].first < y[j].first)) {
if (res.empty() || res.back().second != x[i].first - 1) {
res.push_back(x[i]);
} else {
res.back().second = x[i].second;
}
i++;
} else {
if (res.empty() || res.back().second != y[j].first - 1) {
res.push_back(y[j]);
} else {
res.back().second = y[j].second;
}
j++;
}
}
return res;
}
struct state {
vector<pair<int, int>> interval;
int len;
state(int N) {
if (N == -1) {
len = 0;
interval = {};
} else {
len = N;
interval = {make_pair(1, N)};
}
}
void add(pair<int, int> p) {
interval = merge_vec(interval, {p});
len += p.second - p.first + 1;
}
bool in(int x) {
for (auto& p : interval) {
if (p.first <= x && x <= p.second) {
return true;
}
}
return false;
}
pair<state, state> split(int delta) {
state L(-1);
state R(-1);
if (len == 0) {
return {L, R};
}
for (auto& p : interval) {
if (L.len + p.second - p.first + 1 <= (len + delta) / 2) {
L.add(p);
} else if (L.len >= (len + delta) / 2) {
R.add(p);
} else {
L.add({p.first, p.first + (len + delta) / 2 - L.len});
assert(!L.interval.empty());
R.add({L.interval.back().second + 1, p.second});
}
}
return {L, R};
}
vector<int> all() {
vector<int> v;
for (auto& p : interval) {
for (int i = p.first; i <= p.second; i++) {
v.push_back(i);
}
}
return v;
}
};
state Merge(state p, state q) {
state ret(-1);
ret.interval = merge_vec(p.interval, q.interval);
ret.len = p.len + q.len;
return ret;
}
pair<int, int> solve(int N, int X) {
state good(N);
state bad(-1);
while (good.len + bad.len > 3) {
auto good_split = good.split(0);
state good_L = good_split.first;
state good_R = good_split.second;
auto bad_split = bad.split(1);
state bad_L = bad_split.first;
state bad_R = bad_split.second;
int f;
if (X == -1) {
f = receive();
} else {
f = send(good_L.in(X) || bad_L.in(X));
}
if (f == 0) {
good = Merge(good_R, bad_R);
bad = good_L;
} else {
good = Merge(good_L, bad_L);
bad = good_R;
}
}
vector<int> nums = Merge(good, bad).all();
if (nums.size() == 3) {
if (X != -1) {
if (nums[0] == X) {
send(0);
send(0);
send(0);
send(0);
}
if (nums[1] == X) {
send(0);
send(1);
send(1);
send(0);
}
if (nums[2] == X) {
send(1);
send(1);
send(1);
send(1);
}
} else {
vector<vector<int>> f;
f.push_back({0, 0, 0, 0});
f.push_back({0, 1, 1, 0});
f.push_back({1, 1, 1, 1});
vector<int> seq;
seq.push_back(receive());
seq.push_back(receive());
seq.push_back(receive());
seq.push_back(receive());
vector<int> new_nums;
for (int i = 0; i < 3; i++) {
bool ok = true;
for (int j = 1; j < 4; j++) {
if (seq[j] != f[i][j] && seq[j - 1] != f[i][j - 1]) {
ok = false;
}
}
if (ok) {
new_nums.push_back(nums[i]);
}
}
swap(new_nums, nums);
}
}
if (nums.size() == 1) {
return {nums[0], nums[0]};
}
return {nums[0], nums[1]};
}
void encode(int N, int X) {
solve(N, X);
}
pair<int, int> decode(int N) {
return solve(N, -1);
}
