#include <bits/stdc++.h>
#include "communication.h"
using namespace std;
constexpr int MAXBITS = 30;
constexpr int LEN = 116;
int change_index_extremes_equal(int idx) {
switch (idx) {
case 0: return 0;
case 1: return 0;
case 2: return 1;
case 3: return 2;
case 4: return 1;
case 5: return 2;
case 6: return 3;
case 7: return 3;
}
}
vector<int> change_from_idx_eq(int idx, bool preserve) {
if (preserve) {
switch (idx) {
case 0: return {0, 0, 0, 0};
case 1: return {0, 1, 0, 0};
case 2: return {0, 0, 1, 0};
case 3: return {1, 0, 0, 1};
}
} else {
switch (idx) {
case 0: return {1, 0, 0, 0};
case 1: return {1, 0, 1, 0};
case 2: return {0, 0, 0, 1};
case 3: return {0, 1, 0, 1};
}
}
}
int idx_from_change(int sz, vector<int> ch) {
int cnt = 0;
for (int i = 0; i < (1 << sz); i++) {
bool ok = true;
for (int j = 0; j < sz; j++)
ok &= (i >> j) % 4 != 3;
if (!ok)
continue;
bool match = true;
for (int j = 0; j < sz; j++)
match &= ch[j] == (i >> j) % 2;
if (match)
return cnt;
cnt++;
}
}
vector<int> change_from_idx(int sz, int idx) {
int cnt = 0;
vector<int> ans(sz);
for (int i = 0; i < (1 << sz); i++) {
bool ok = true;
for (int j = 0; j < sz; j++)
ok &= (i >> j) % 4 != 3;
if (!ok)
continue;
if (cnt == idx) {
for (int j = 0; j < sz; j++)
ans[j] = (i >> j) % 2;
return ans;
}
cnt++;
}
}
int send_packet(int sz, vector<int> b) {
vector<int> ch(sz);
for (int i = 0; i < sz; i++) {
ch[i] = b[i] ^ send(b[i]);
}
return idx_from_change(sz, ch);
}
void encode(int N, int X) {
X--;
vector<int> bits(MAXBITS);
for (int i = 0; i < MAXBITS; i++)
bits[i] = (X >> i) & 1;
// Sending message
int last = send_packet(4, {bits[0], bits[1], bits[2], bits[3]});
for (int i = 4; i < MAXBITS; i++) {
last = send_packet(4, {bits[i], (last >> 0) & 1, (last >> 1) & 1, (last >> 2) & 1});
}
// 8 states from 4
last = send_packet(4, {(last >> 0) & 1, (last >> 1) & 1, (last >> 2) & 1, (last >> 0) & 1});
last = change_index_extremes_equal(last);
// Solution for N=4
switch (last) {
case 0: send_packet(4, {0, 0, 0, 0}); break;
case 1: send_packet(4, {0, 1, 1, 0}); break;
case 2: send_packet(4, {1, 0, 0, 1}); break;
case 3: send_packet(4, {1, 1, 1, 1}); break;
}
}
pair<int, int> starting_guesses(vector<int> packet) {
int val = packet[0] | 2 * packet[1] | 4 * packet[2] | 8 * packet[3];
switch (val) {
case 0: return {0, 2};
case 1: return {0, 2};
case 2: return {0, 1};
case 3: return {1, 2};
case 4: return {0, 1};
case 5: return {0, 3};
case 6: return {1, 3};
case 7: return {1, 3};
case 8: return {0, 2};
case 9: return {0, 2};
case 10: return {0, 3};
case 11: return {2, 3};
case 12: return {1, 2};
case 13: return {2, 3};
case 14: return {1, 3};
case 15: return {1, 3};
}
}
int solve(int start, vector<int> packets) {
int changed = start;
auto pop = [&]() {
int ans = packets.back();
packets.pop_back();
return ans;
};
// 4 states to 8
{
vector<int> packet = {pop(), pop(), pop(), pop()};
vector<int> changes = change_from_idx_eq(changed, packet[0] == packet[3]);
reverse(changes.begin(), changes.end());
changed = (changes[1] ^ packet[1]) * 4 | (changes[2] ^ packet[2]) * 2 | (changes[3] ^ packet[3]);
}
// 8 states to full message
int ans = 0;
while (!packets.empty()) {
vector<int> packet = {pop(), pop(), pop(), pop()};
vector<int> changes = change_from_idx(4, changed);
reverse(changes.begin(), changes.end());
if (!packets.empty()) {
changed = (changes[0] ^ packet[0]) * 4 | (changes[1] ^ packet[1]) * 2 | (changes[2] ^ packet[2]);
ans <<= 1;
ans |= changes[3] ^ packet[3];
} else {
for (auto i: {0, 1, 2, 3}) {
ans <<= 1;
ans |= changes[i] ^ packet[i];
}
}
}
return ans;
}
pair<int, int> decode(int N) {
vector<int> packets(LEN);
for (int i = 0; i < LEN; i++)
packets[i] = receive();
vector<int> head(packets.end() - 4, packets.end());
vector<int> tail(packets.begin(), packets.end() - 4);
auto [guess_1, guess_2] = starting_guesses(head);
return {min(N, solve(guess_1, tail) + 1), min(N, solve(guess_2, tail) + 1)};
}
