#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
struct Range {
int l, r;
Range(int l, int r) : l(l), r(r) {}
int size() { return r - l + 1; }
pair<Range, Range> split(int qtd) {
return {Range(l, l + qtd - 1), Range(l + qtd, r) };
}
friend ostream& operator<<(ostream& os, const Range& r) {
return os << '<' <<r.l << ", " << r.r << '>';
}
};
int get_total_size(vector<Range> ranges) {
int ans = 0;
for(Range r : ranges)
ans += r.size();
return ans;
}
pair<vector<Range>, vector<Range>> split(vector<Range> ranges) {
int sz = get_total_size(ranges);
vector<Range> g[2];
int now = 0;
for(Range r : ranges) {
if(now + r.size() <= (sz+1)/2)
g[0].push_back(r), now += r.size();
else if(now < (sz+1)/2) {
auto [r1, r2] = r.split((sz+1)/2 - now);
g[0].push_back(r1);
g[1].push_back(r2);
now = (sz+1)/2;
} else
g[1].push_back(r);
}
return {g[0], g[1]};
}
pair<int,int> answer(vector<Range> ranges) {
vector<int> ans;
for(Range r : ranges)
for(int i = r.l; i <= r.r; i++)
ans.push_back(i);
return {ans[0], ans[1]};
}
pair<int,int> build_decode(vector<Range> head, vector<Range> left, vector<Range> right) {
if(get_total_size(head) <= 2 && !get_total_size(left) && !get_total_size(right))
return answer(head);
if(get_total_size(head) <= 1 && get_total_size(left) <= 1 && get_total_size(right) <= 1) {
if(receive())
return {head[0].l, left[0].l};
else
return {head[0].l, right[0].l};
}
if(get_total_size(head) <= 2 && get_total_size(left) <= 1 && !get_total_size(right)) {
if(receive() == 1)
return answer(head);
if(receive() == 0)
return {head[0].l, left[0].l};
else if(head.size() == 2)
return {head[1].l, left[0].l};
else
return {head[0].r, left[0].l};
}
// assumes there is always the same number of people on the left and right
int n = (int)head.size();
vector<Range> g[2];
pair<vector<Range>, vector<Range>> spl = split(head);
g[0] = spl.first;
g[1] = spl.second;
if(get_total_size(left) > get_total_size(right))
swap(g[0], g[1]);
int k = receive();
vector<Range> &pre = k ? right : left;
spl = split(g[!k]);
int m = g[!k].size();
vector<Range> f1 = spl.first;
vector<Range> f2 = spl.second;
g[k].insert(g[k].end(), pre.begin(), pre.end());
return build_decode(g[k], f1, f2);
}
bool in(vector<Range> ranges, int x) {
for(Range r : ranges)
if(r.l <= x && x <= r.r)
return true;
return false;
}
void build_encode(vector<Range> head, vector<Range> left, vector<Range> right, int secret) {
if(get_total_size(head) <= 2 && !get_total_size(left) && !get_total_size(right))
return;
if(get_total_size(head) <= 1 && get_total_size(left) <= 1 && get_total_size(right) <= 1) {
if(in(left, secret))
send(0);
else // se tiver em left ou right signifca que deu errado antes entao to garantido
send(1); // se tiver em head nao importa
return;
}
if(get_total_size(head) <= 2 && get_total_size(left) <= 1 && !get_total_size(right)) {
if(in(left, secret)) {
send(0), send(0); // so importa que vou pra esquerda agr, dps fds
return;
} else {
int nxt = send(1);
if(nxt) return; // fui pra direita entao ja posso terminar
if(head[0].l == secret)
send(0);
else
send(1);
return;
}
}
// assumes there is always the same number of people on the left and right
int n = (int)head.size();
vector<Range> g[2];
pair<vector<Range>, vector<Range>> spl = split(head);
g[0] = spl.first;
g[1] = spl.second;
if(get_total_size(left) > get_total_size(right))
swap(g[0], g[1]);
int k;
if(in(left, secret)) {
k = 0;
send(0); // anterior foi mudado entao garanto movimento aqui
} else if(in(right, secret)) {
k = 1;
send(1); // anterior foi mudado entao garanto movimento aqui
} else {
int tento = in(g[1], secret);
k = send(tento); // tento ir pra aquele lado mas se nao for tenho que mover pro outro
}
vector<Range> &pre = k ? right : left;
spl = split(g[!k]);
int m = g[!k].size();
vector<Range> f1 = spl.first;
vector<Range> f2 = spl.second;
g[k].insert(g[k].end(), pre.begin(), pre.end());
build_encode(g[k], f1, f2, secret);
}
void encode(int N, int X) {
vector<Range> a = {Range(1, N)};
vector<int> s;
return build_encode(a, {}, {}, X);
}
std::pair<int, int> decode(int N) {
vector<Range> a = {Range(1, N)};
vector<int> s;
return build_decode(a, {}, {});
}
