#include"communication.h" #include <bits/stdc++.h> using namespace std; int opt[7]={0, 0, 1, 0, 0, 1, 0}; int val=0; int ab[30]; bool has[5000000]; int n; int lv=0; vector<int> vals; int checkBit(int bit) { if(!val) return receive(); else return send((val>>bit)&1); } int checkVec(vector<int> &vec) { if(!val) return receive(); for(auto v : vec) if(vals[v]==val) return send(1); return send(0); } void dfs(int val, int i) { if(i==30) { if(val>=1&&val<=n) vals.push_back(val); return; } dfs(val|(ab[i]<<i), i+1); if(((val>>(i-1))&1)==ab[i-1]) dfs(val|(!ab[i]<<i), i+1); } int cmpl(int a, int b) { return (a==lv)&&(b!=lv); } vector<int> solve(vector<int> vc) { int off=1; int an=0; int i=1; vector<int> qs; qs.push_back(vc[0]); if(!lv) { off=0; qs.clear(); i=0; } for(;i<3;i++) { qs.push_back(vc[opt[off+an]]); vector<int> vq[2]; for(auto v : vc) { vq[v!=qs.back()].push_back(v); } int ca=checkVec(vq[0]); an|=ca<<i; off|=1<<i; } vector<int> nv; for(auto v : vc) { int could=0; for(int msk2=0;msk2<8;msk2++) { if(((msk2&0b110)==0b110)||((msk2&0b011)==0b011)) continue; int cc=1; for(int i=0;i<3;i++) { int cq=qs[i]; int ca=(an>>i)&1; int cl=(msk2>>i)&1; if((cq==v)^ca^cl) { cc=0; break; } } if(cc) { could=1; break; } } if(could) nv.push_back(v); } return nv; } pair<int, int> rdecode(int N, int r) { vals.clear(); n=N; if(r) val=0; lv=0; for(int i=0;i<30;i++) ab[i]=checkBit(i); dfs(0, 1); dfs(1, 1); vector<int> vl[2]; for(int i=0;i<(int)vals.size();i++) { vl[((vals[i]>>29)&1)!=ab[29]].push_back(i); } while((int)vl[0].size()+(int)vl[1].size()>3) { vector<int> vc[2]; int id=0; for(auto v : vl[0]) vc[id^=1].push_back(v); for(auto v : vl[1]) vc[id^=1].push_back(v); if(!checkVec(vc[0])) swap(vc[0], vc[1]); vl[0]=vc[0]; vector<int> nv; for(auto v : vl[1]) has[v]=1; for(auto v : vc[1]) { if(!has[v]) nv.push_back(v); } for(auto v : vl[1]) has[v]=0; vl[1]=nv; lv=nv[0]; } vector<int> vc; for(auto v : vl[0]) vc.push_back(v); for(auto v : vl[1]) vc.push_back(v); sort(vc.begin(), vc.end(), cmpl); if((int)vc.size()==3) vc=solve(vc); if((int)vc.size()==1) vc.push_back(vc[0]); return {vals[vc[0]], vals[vc[1]]}; } void encode(int N, int X) { val=X; rdecode(N, 0); } pair<int, int> decode(int N) { return rdecode(N, 1); }