#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> b;
void send_(int x)
{
int y=send(x);
b.push_back(y);
}
int send_num(int x)
{
b.clear();
if(x==0)
{
for(int i=0; i<4; i++)
send_(0);
}
if(x==1)
{
for(int i=0; i<4; i++)
send_(1);
}
if(x==2)
{
send_(1);
send_(0);
send_(0);
send_(1);
}
if(x==3)
{
send_(0);
send_(1);
send_(1);
send_(0);
}
int y=0;
for(int i=0;i<4;i++)
y+=b[i]*(1<<i);
return y;
}
int num;
vector<int> v[200001];
void rec(deque<pair<int,int> > d)
{
deque<pair<int,int> > s[4];
int cnt=0;
for(int i=0; i<d.size(); i++)
cnt+=d[i].second-d[i].first+1;
if(cnt<=2)
{
return;
}
for(int i=0; i<4; i++)
{
int sz=cnt/4;
if(cnt%4>=i+1)sz++;
while(sz>d[0].second-d[0].first+1)
{
pair<int,int> p=d[0];
d.pop_front();
sz-=d[0].second-d[0].first+1;
s[i].push_back(p);
}
pair<int,int> p=d[0];
p.second=p.first+sz-1;
s[i].push_back(p);
int len=d[0].second-d[0].first+1;
if(len==sz)d.pop_front();
else d[0].first+=sz;
}
int curr=0;
for(int i=0;i<4;i++)
{
for(int j=0;j<s[i].size();j++)
{
pair<int,int> p=s[i][j];
if(p.first<=num&&num<=p.second)
curr=i;
}
}
deque<pair<int,int> > r;
int h=send_num(curr);
for(int i=0;i<v[h].size();i++)
{
int c=v[h][i];
for(int j=0;j<s[c].size();j++)
{
r.push_back(s[c][j]);
}
}
rec(r);
}
void connect(int x,int y)
{
for(int i=0; i<16; i++)
{
bool pos=1;
for(int j=0; j<=2; j++)
{
int b1=(1<<j)&i;
int b2=(1<<(j+1))&i;
if(b1&&b2)pos=0;
}
if(pos==0)continue;
//cout<<(x^i)<<" - "<<y<<endl;
v[x^i].push_back(y);
}
}
void encode(int N, int X)
{
connect(0,0);
connect(15,1);
connect(9,2);
connect(6,3);
/*for(int i=0;i<16;i++)
{
cout<<i<<" : ";
for(int j=0;j<v[i].size();j++)
cout<<v[i][j]<<" ";
cout<<endl;
}*/
num=X;
rec({{1,N}});
}
int get_num()
{
int ans=0;
for(int i=0;i<4;i++)
{
int x=receive();
ans+=x*(1<<i);
}
return ans;
}
deque<pair<int,int> > rec2(deque<pair<int,int> > d)
{
deque<pair<int,int> > s[4];
int cnt=0;
for(int i=0; i<d.size(); i++)
cnt+=d[i].second-d[i].first+1;
if(cnt<=2)
{
if(d.size()==1)return {d[0]};
return {{d[0].first,d[1].first}};
}
for(int i=0; i<4; i++)
{
int sz=cnt/4;
if(cnt%4>=i+1)sz++;
while(sz>d[0].second-d[0].first+1)
{
pair<int,int> p=d[0];
d.pop_front();
sz-=d[0].second-d[0].first+1;
s[i].push_back(p);
}
pair<int,int> p=d[0];
p.second=p.first+sz-1;
s[i].push_back(p);
int len=d[0].second-d[0].first+1;
if(len==sz)d.pop_front();
else d[0].first+=sz;
}
deque<pair<int,int> > r;
int h=get_num();
for(int i=0;i<v[h].size();i++)
{
int c=v[h][i];
for(int j=0;j<s[c].size();j++)
{
r.push_back(s[c][j]);
}
}
return rec2(r);
}
std::pair<int, int> decode(int N)
{
connect(0,0);
connect(15,1);
connect(9,2);
connect(6,3);
return rec2({{1,N}})[0];
}
