#include <vector>
#include <cstdint>
#include <algorithm>
using namespace std;
// 强混合哈希函数
uint32_t mix_hash(uint32_t x) {
x ^= x >> 16;
x *= 0x85ebca6b;
x ^= x >> 13;
x *= 0xc2b2ae35;
x ^= x >> 16;
return x;
}
vector<bool> send_packet(vector<bool> A);
void send_message(vector<bool> M, vector<bool> C) {
int S = M.size();
int D = (S + 15) / 16;
vector<int> safe_cols;
for(int i = 0; i < 31; ++i) {
if(!C[i]) safe_cols.push_back(i);
}
vector<bool> padded_M = M;
while(padded_M.size() < D * 16) {
padded_M.push_back(false);
}
vector<vector<bool>> B(D);
int idx = 0;
for(int p = 0; p < D; ++p) {
vector<bool> A(31, false);
for(int i = 0; i < 16; ++i) {
A[safe_cols[i]] = padded_M[idx++];
}
B[p] = send_packet(A);
}
uint32_t H[31];
for(int i = 0; i < 31; ++i) {
uint32_t hash_val = S;
for(int p = 0; p < D; ++p) {
hash_val = mix_hash(hash_val ^ (B[p][i] ? 1 : 0));
}
H[i] = hash_val;
}
uint32_t Target = 0;
for(int j = 0; j < 16; ++j) {
Target ^= H[safe_cols[j]];
}
vector<bool> P1(31, false), P2(31, false);
for(int j = 0; j < 16; ++j) {
uint32_t v = (Target >> (2 * j)) & 3;
P1[safe_cols[j]] = v & 1;
P2[safe_cols[j]] = (v >> 1) & 1;
}
send_packet(P1);
send_packet(P2);
}
void get_subsets(const vector<int>& cols, int k, vector<pair<uint32_t, int>>& res, const uint32_t* H, const uint32_t* V, int rank_offset) {
int n = cols.size();
int mask = (1 << k) - 1;
while(mask < (1 << n)) {
uint32_t val = 0;
int rank = rank_offset;
for(int i = 0; i < n; ++i) {
if((mask >> i) & 1) {
val ^= H[cols[i]] ^ (V[cols[i]] << (2 * rank));
rank++;
}
}
res.push_back({val, mask});
if(k == 0) break;
uint32_t c = mask & -mask;
uint32_t r = mask + c;
mask = (((r ^ mask) >> 2) / c) | r;
}
}
vector<bool> receive_message(vector<vector<bool>> R) {
int P = R.size();
int D = P - 2;
int min_S = max(1, (D - 1) * 16 + 1);
int max_S = min(1024, D * 16);
uint32_t V[31] = {0};
for(int i = 0; i < 31; ++i) {
V[i] = (R[D][i] ? 1 : 0) | ((R[D+1][i] ? 1 : 0) << 1);
}
vector<int> left_cols, right_cols;
for(int i = 0; i < 16; ++i) left_cols.push_back(i);
for(int i = 16; i < 31; ++i) right_cols.push_back(i);
for(int S_guess = min_S; S_guess <= max_S; ++S_guess) {
uint32_t H[31];
for(int i = 0; i < 31; ++i) {
uint32_t hash_val = S_guess;
for(int p = 0; p < D; ++p) {
hash_val = mix_hash(hash_val ^ (R[p][i] ? 1 : 0));
}
H[i] = hash_val;
}
for(int k = 0; k <= 16; ++k) {
if(k > 16 || (16 - k) > 15) continue;
vector<pair<uint32_t, int>> left_res, right_res;
get_subsets(left_cols, k, left_res, H, V, 0);
get_subsets(right_cols, 16 - k, right_res, H, V, k);
sort(left_res.begin(), left_res.end());
sort(right_res.begin(), right_res.end());
int i = 0, j = 0;
while(i < left_res.size() && j < right_res.size()) {
if(left_res[i].first == right_res[j].first) {
int maskL = left_res[i].second;
int maskR = right_res[j].second;
vector<int> S_cols;
for(int m = 0; m < 16; ++m) if((maskL >> m) & 1) S_cols.push_back(left_cols[m]);
for(int m = 0; m < 15; ++m) if((maskR >> m) & 1) S_cols.push_back(right_cols[m]);
vector<bool> M;
int idx = 0;
for(int p = 0; p < D; ++p) {
for(int c = 0; c < 16; ++c) {
if(idx < S_guess) M.push_back(R[p][S_cols[c]]);
idx++;
}
}
return M;
} else if(left_res[i].first < right_res[j].first) {
i++;
} else {
j++;
}
}
}
}
return {};
}
