#include <bits/stdc++.h>
// mrrrowwww meeowwwww :3
// go play vivid/stasis! !! !!! https://vividstasis.gay
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = []{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
return 0;
}();
struct Ranges {
int len;
vector<pair<int, int>> ranges;
Ranges() : len(0) {}
Ranges(int a, int b) : len(b - a), ranges { { a, b } } {}
bool contains(int v) const {
int l = 0, r = ranges.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (ranges[mid].f <= v) r = mid;
else l = mid + 1;
}
return l < ranges.size() && ranges[l].f <= v && v < ranges[l].s;
}
Ranges take_from_top(int take) {
Ranges res;
res.len = take;
len -= take;
int b_len = len;
int to_pop = 0;
fo(i, 0, ranges.size()) {
if (b_len >= ranges[i].s - ranges[i].f) {
b_len -= ranges[i].s - ranges[i].f;
} else if (b_len == 0) {
res.ranges.pb(ranges[i]);
to_pop++;
} else {
res.ranges.pb({ ranges[i].f + b_len, ranges[i].s });
ranges[i].s = ranges[i].f + b_len;
}
}
while (to_pop--) ranges.pop_back();
return res;
}
void merge(const Ranges &other) {
len += other.len;
fo(i, 0, other.ranges.size()) {
if (ranges.size() && ranges.back().s == other.ranges[i].f) {
ranges.back().s = other.ranges[i].s;
} else {
ranges.pb(other.ranges[i]);
}
}
}
};
void decode_bit(Ranges &corr_b, Ranges &corr_t, Ranges &wron_b, Ranges &wron_t, bool bit) {
if (bit) {
corr_b.merge(wron_b);
wron_b = move(corr_t);
} else {
corr_t.merge(wron_t);
wron_b = move(corr_b);
corr_b = move(corr_t);
}
corr_t = corr_b.take_from_top(corr_b.len / 2);
wron_t = wron_b.take_from_top((wron_b.len + 1) / 2);
}
int send(int);
void encode(int n, int x) {
Ranges corr_b(1, n + 1), corr_t = corr_b.take_from_top(corr_b.len / 2);
Ranges wron_b, wron_t;
while (corr_b.len + corr_t.len + wron_b.len + wron_t.len > 2) {
bool bit = send(corr_b.contains(x) || wron_b.contains(x));
decode_bit(corr_b, corr_t, wron_b, wron_t, bit);
}
vector<int> res;
for (auto [a, b] : corr_b.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : corr_t.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : wron_b.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : wron_t.ranges) fo(i, a, b) res.pb(i);
cerr << res[0] << ' ' << res[1] << endl;
}
int receive();
pair<int, int> decode(int n) {
Ranges corr_b(1, n + 1), corr_t = corr_b.take_from_top(corr_b.len / 2);
Ranges wron_b, wron_t;
while (corr_b.len + corr_t.len + wron_b.len + wron_t.len > 2) {
bool bit = receive();
decode_bit(corr_b, corr_t, wron_b, wron_t, bit);
}
vector<int> res;
for (auto [a, b] : corr_b.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : corr_t.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : wron_b.ranges) fo(i, a, b) res.pb(i);
for (auto [a, b] : wron_t.ranges) fo(i, a, b) res.pb(i);
return { res[0], res[1] };
}
