#include<bits/stdc++.h>
#include"communication.h"
#define recieve receive
using namespace std;
struct Node{
Node *lf, *rf;
int val, lz;
Node(int v, int ll, int rr){
val = (rr-ll+1)*v;
lz = -1;
lf = rf = NULL;
}
void unlazy(int l, int r){
if(lz==-1) return;
val = lz*(r-l+1);
if(l != r){
int mid = (l+r)/2;
if(!lf) lf = new Node(1, l, mid);
if(!rf) rf = new Node(1, mid+1, r);
lf->lz = lz;
rf->lz = lz;
}
lz = -1;
}
void update(int l, int r, int tl, int tr, int v){
unlazy(tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
lz = v;
unlazy(tl, tr);
return;
}
int mid = (tl+tr)/2;
if(!lf) lf = new Node(1, tl, mid);
if(!rf) rf = new Node(1, mid+1, tr);
lf->update(l, r, tl, mid, v);
rf->update(l, r, mid+1, tr, v);
val = lf->val+rf->val;
return;
}
int query(int l, int r, int tl, int tr){
unlazy(tl, tr);
if(l > tr or tl > r) return 0;
if(l <= tl and tr <= r) return val;
int mid = (tl+tr)/2;
if(!lf) lf = new Node(1, tl, mid);
if(!rf) rf = new Node(1, mid+1, tr);
return lf->query(l, r, tl, mid)+rf->query(l, r, mid+1, tr);
}
int busca(int l, int r, int v){
unlazy(l, r);
if(l == r) return l;
int mid = (l+r)/2;
if(!lf) lf = new Node(1, l, mid);
if(lf->val >= v) return lf->busca(l, mid, v);
else{
v -= lf->val;
if(!rf) rf = new Node(1, mid+1, r);
return rf->busca(mid+1, r, v);
}
}
};
void encode(int n, int x) {
Node seg(1, 1, n);
while(seg.query(1, n, 1, n) > 2){
int tot = seg.query(1, n, 1, n);
int m1 = tot/3, m2 = 2*tot/3;
int l = 1, p1 = seg.busca(1, n, m1), p2 = seg.busca(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(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 <= p2){
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(p1+1, n, 1, n, 0);
}
else if(a == 0 and b == 1){
seg.update(p1+1, p2, 1, n, 0);
}
else if(a == 1 and b == 0){
seg.update(1, p1, 1, n, 0);
}
else{
seg.update(1, p1, 1, n, 0);
}
}
return;
}
std::pair<int, int> decode(int n) {
Node seg(1, 1, n);
while(seg.query(1, n, 1, n) > 2){
int tot = seg.query(1, n, 1, n);
int m1 = tot/3, m2 = 2*tot/3;
int l = 1, p1 = seg.busca(1, n, m1), p2 = seg.busca(1, n, m2), r = n;
int x = recieve();
if(x == 1){
x = recieve();
if(x == 1){
seg.update(p2+1, n, 1, n, 0);
continue;
}
}
int a = recieve();
int b = recieve();
if(a == 0 and b == 0){
seg.update(p1+1, n, 1, n, 0);
}
else if(a == 0 and b == 1){
seg.update(p1+1, p2, 1, n, 0);
}
else if(a == 1 and b == 0){
seg.update(1, p1, 1, n, 0);
}
else{
seg.update(1, p1, 1, n, 0);
}
}
//cout << seg.busca(1, n, 1) << ' ' << seg.busca(1, n, 2) << endl;
return {seg.busca(1, n, 1), seg.busca(1, n, 2)};
}
