#include <vector>
#include <cstdint>
#include <algorithm>
using namespace std;
vector<bool> send_packet(vector<bool> A);
// 强位混合哈希函数，避免任何冲突
uint64_t mix_hash(uint64_t x) {
x ^= x >> 30;
x *= 0xbf58476d1ce4e5b9ULL;
x ^= x >> 27;
x *= 0x94d049bb133111ebULL;
x ^= x >> 31;
return x;
}
// 提取指定列的哈希值，动态包含反馈历史
uint16_t get_h(int c, int round, int S, const vector<vector<bool>>& R) {
uint64_t state = S ^ (round * 0x123456789ABCDEFULL) ^ c;
for (size_t i = 0; i < R.size(); ++i) {
state = mix_hash(state ^ (R[i][c] ? 0x9e3779b97f4a7c15ULL : 0));
}
return (state >> 16) & 0xFFFF;
}
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<vector<bool>> R;
int idx = 0;
// 阶段1：发送原始数据包
for (int p = 0; p < D; ++p) {
vector<bool> A(31, false);
for (int i = 0; i < 16; ++i) {
if (idx < S) A[safe_cols[i]] = M[idx++];
}
R.push_back(send_packet(A));
}
// 阶段2：发送 4 轮基于反馈的验证包
for (int round = 0; round < 4; ++round) {
uint16_t h[31];
for (int c = 0; c < 31; ++c) {
h[c] = get_h(c, round, S, R);
}
uint16_t target = 0;
for (int i = 0; i < 16; ++i) target ^= h[safe_cols[i]];
vector<bool> A(31, false);
for (int i = 0; i < 16; ++i) A[safe_cols[i]] = (target >> i) & 1;
R.push_back(send_packet(A));
}
}
// 中途相遇子集枚举生成器
void get_subsets(const vector<int>& cols, int k, vector<pair<uint64_t, int>>& res,
const uint64_t* H, const uint64_t* V, int rank_offset) {
int n = cols.size();
int mask = (1 << k) - 1;
while (mask < (1 << n)) {
uint64_t val = 0;
int rank = rank_offset;
for (int i = 0; i < n; ++i) {
if ((mask >> i) & 1) {
int c = cols[i];
val ^= H[c] ^ (V[c] << rank);
rank++;
}
}
res.push_back({val, mask});
if (k == 0) break;
uint32_t c_mask = mask & -mask;
uint32_t r = mask + c_mask;
mask = (((r ^ mask) >> 2) / c_mask) | r;
}
}
vector<bool> receive_message(vector<vector<bool>> R) {
int Q = R.size();
int D = Q - 4; // 推算得知真实的数据包总数
int min_S = max(1, (D - 1) * 16 + 1);
int max_S = D * 16;
// 猜测可能的原始数据量 S
for (int S_guess = min_S; S_guess <= max_S; ++S_guess) {
uint16_t h0[31], h1[31], h2[31], h3[31];
vector<vector<bool>> R0(R.begin(), R.begin() + D);
for (int c = 0; c < 31; ++c) h0[c] = get_h(c, 0, S_guess, R0);
vector<vector<bool>> R1 = R0; R1.push_back(R[D]);
for (int c = 0; c < 31; ++c) h1[c] = get_h(c, 1, S_guess, R1);
vector<vector<bool>> R2 = R1; R2.push_back(R[D+1]);
for (int c = 0; c < 31; ++c) h2[c] = get_h(c, 2, S_guess, R2);
vector<vector<bool>> R3 = R2; R3.push_back(R[D+2]);
for (int c = 0; c < 31; ++c) h3[c] = get_h(c, 3, S_guess, R3);
uint64_t H[31];
for (int c = 0; c < 31; ++c) {
H[c] = ((uint64_t)h3[c] << 48) | ((uint64_t)h2[c] << 32) | ((uint64_t)h1[c] << 16) | h0[c];
}
uint64_t V[31];
for (int c = 0; c < 31; ++c) {
uint64_t v0 = R[D][c] ? 1 : 0;
uint64_t v1 = R[D+1][c] ? 1 : 0;
uint64_t v2 = R[D+2][c] ? 1 : 0;
uint64_t v3 = R[D+3][c] ? 1 : 0;
V[c] = (v3 << 48) | (v2 << 32) | (v1 << 16) | v0;
}
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 k = 0; k <= 16; ++k) {
if (k > 16 || (16 - k) > 15) continue;
vector<pair<uint64_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_ret;
int msg_idx = 0;
for (int p = 0; p < D; ++p) {
for (int c = 0; c < 16; ++c) {
if (msg_idx < S_guess) {
M_ret.push_back(R[p][S_cols[c]]);
msg_idx++;
}
}
}
return M_ret; // 一旦符合反馈条件便立刻解构消息输出
} else if (left_res[i].first < right_res[j].first) {
i++;
} else {
j++;
}
}
}
}
return {};
}
