/**
* Well, i've seen this trick in an Olympic Maths combinactorics book (Olympic
* Combinactorics Book1, i guess), though i guess this communication problem would
* still be pretty interesting for those who haven't. Suppose that set A contains
* the original N bits, set B contains ceil(log_2(n)) bits and set C contains a
* single bit, which is the xor of all bits in B.
*
* We solve this problem by using the fact that each int has a UNIQUE binary repr.
* The i-th bit in B equals the xor of all bits in A (whose index(<=N, >0)'s i-th
* bit is a 1). The sole bit in set C can just be the xor of all bits in B. 1-indexed
* is used to ensure that if a bit in A is corruputed, at least 1 bit in B is
* changed.
*
* Q: log_2(n)
* Implementation 1
*/
#include <bits/stdc++.h>
#include "transfer.h"
typedef std::vector<int> vec;
const int N1 = 63, B1 = 6, SIZE1 = 70;
const int N2 = 255, B2 = 8, SIZE2 = 264;
vec get_attachment(vec source) {
int n = source.size(), B = (n == N2 ? B2 : B1);
vec encoded(B + 1, 0);
for (int k = 0; k < n; k++) {
for (int k_copy = k + 1, bit = 0; k_copy > 0; k_copy >>= 1, bit++) {
if (k_copy & 1)
encoded[bit] ^= source[k];
}
}
for (int k = 0; k < B; k++)
encoded[B] ^= encoded[k];
return encoded;
}
vec retrieve(vec data) {
int n = (data.size() == SIZE2 ? N2 : N1), B = (n == N2 ? B2 : B1);
std::vector<bool> correct(B);
vec compute(B, 0);
for (int k = 0; k < n; k++) {
for (int k_copy = k + 1, bit = 0; k_copy > 0; k_copy >>= 1, bit++) {
if (k_copy & 1)
compute[bit] ^= data[k];
}
}
bool set_B_xor = 0;
for (int i = 0; i < B; i++)
correct[i] = (compute[i] == data[i + n]), set_B_xor ^= data[i + n];
bool AB_correct = true;
for (int i = 0; i < B && AB_correct; i++)
AB_correct &= correct[i];
if (!AB_correct && set_B_xor == data[n + B]) {
int corrupt_bit = 0;
for (int k = 0; k < B; k++) {
if (!correct[k])
corrupt_bit |= (1 << k);
}
data[corrupt_bit - 1] ^= 1;
}
data.resize(n); // truncate the array
return data;
}
