#include<bits/stdc++.h>
#include"communication.h"
#define recieve receive
using namespace std;
const int N = 20010;
struct Segtree{
int tree[4*N], lazy[4*N], lf[4*N], rf[4*N];
int nx;
void build(int val, int l, int r){
memset(lazy, -1, sizeof lazy);
memset(lf, -1, sizeof lf);
memset(rf, -1, sizeof rf);
tree[1] = (r-l+1);
nx = 2;
}
void unlazy(int node, int l, int r){
if(lazy[node] == -1) return;
tree[node] = (r-l+1)*lazy[node];
if(l != r){
int mid = (l+r)/2;
if(lf[node] == -1){
lf[node] = nx;
nx++;
tree[lf[node]] = (mid-l+1);
}
if(rf[node] == -1){
rf[node] = nx;
nx++;
tree[rf[node]] = r-mid;
}
lazy[lf[node]] = lazy[rf[node]] = lazy[node];
}
lazy[node] = -1;
}
void update(int node, int l, int r, int tl, int tr, int val){
unlazy(node, tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
lazy[node] = val;
unlazy(node, tl, tr);
return;
}
int mid = (tl+tr)/2;
if(lf[node] == -1){
lf[node] = nx;
nx++;
tree[lf[node]] = (mid-tl+1);
lazy[lf[node]] = -1;
}
if(rf[node] == -1){
rf[node] = nx;
nx++;
tree[rf[node]] = tr-mid;
lazy[rf[node]] = -1;
}
update(lf[node], l, r, tl, mid, val);
update(rf[node], l, r, mid+1, tr, val);
tree[node] = tree[lf[node]]+tree[rf[node]];
return;
}
int query(int node, int l, int r, int tl, int tr){
unlazy(node, tl, tr);
if(l > tr or tl > r) return 0;
return tree[node];
}
int busca(int node, int l, int r,int val){
unlazy(node, l, r);
if(l == r) return l;
int mid = (l+r)/2;
if(lf[node] == -1){
lf[node] = nx;
nx++;
tree[lf[node]] = mid-l+1;
lazy[lf[node]] = -1;
}
if(tree[lf[node]]>= val) return busca(lf[node], l, mid, val);
if(rf[node] == -1){
rf[node] = nx;
nx++;
tree[rf[node]] = r-mid;
lazy[rf[node]] = -1;
}
return busca(rf[node], mid+1, r, val-tree[lf[node]]);
}
} seg;
void encode(int n, int x) {
seg.build(1, 1, n);
while(seg.query(1, 1, n, 1, n) > 2){
int tot = seg.query(1, 1, n, 1, n);
int m1 = tot/3, m2 = 2*tot/3;
int l = 1, p1 = seg.busca(1, 1, n, m1), p2 = seg.busca(1, 1, n, m2), r = n;
//cout << tot << ' ' << l << ' ' << p1 << ' ' << p2 << ' ' << r << endl;
if(l <= x and x <= p2){
int t = send(1);
if(t == 1){
t = send(1);
if(t == 1){
seg.update(1, p2+1, n, 1, n, 0);
continue;
}
}
}
else{
int t = send(0);
if(t == 1) send(0);
}
int a, b;
if(p1 < x and x <= n){
a = send(1);
}
else{
a = send(0);
}
if(p1 < x and x <= p2){
b = send(0);
}
else{
b = send(1);
}
if(a == 0 and b == 0){
seg.update(1, p1+1, n, 1, n, 0);
}
else if(a == 0 and b == 1){
seg.update(1, p1+1, p2, 1, n, 0);
}
else if(a == 1 and b == 0){
seg.update(1, 1, p1, 1, n, 0);
}
else{
seg.update(1, 1, p1, 1, n, 0);
}
}
return;
}
std::pair<int, int> decode(int n) {
seg.build(1, 1, n);
while(seg.query(1, 1, n, 1, n) > 2){
int tot = seg.query(1, 1, n, 1, n);
int m1 = tot/3, m2 = 2*tot/3;
int l = 1, p1 = seg.busca(1, 1, n, m1), p2 = seg.busca(1, 1, n, m2), r = n;
int x = recieve();
if(x == 1){
x = recieve();
if(x == 1){
seg.update(1, p2+1, n, 1, n, 0);
continue;
}
}
int a = recieve();
int b = recieve();
if(a == 0 and b == 0){
seg.update(1, p1+1, n, 1, n, 0);
}
else if(a == 0 and b == 1){
seg.update(1, p1+1, p2, 1, n, 0);
}
else if(a == 1 and b == 0){
seg.update(1, 1, p1, 1, n, 0);
}
else{
seg.update(1, 1, p1, 1, n, 0);
}
}
//cout << seg.busca(1, n, 1) << ' ' << seg.busca(1, n, 2) << endl;
return {seg.busca(1, 1, n, 1), seg.busca(1, 1, n, 2)};
}
