#include <vector>
#include <random>
#include <cstdint>
using namespace std;
// 由评测系统提供的外部函数
extern std::vector<bool> send_packet(std::vector<bool> A);
// 固定一个对抗者无法知道的随机种子
const uint32_t SEED = 13371337;
const uint32_t MOD_MASK = 0x7FFFFFFF;
void send_message(std::vector<bool> M, std::vector<bool> C) {
int S = M.size();
vector<bool> buffer;
// 1. 放入消息本身
for (int i = 0; i < S; ++i) {
buffer.push_back(M[i]);
}
// 2. 填充使其达到 1025 位 (先追加一个 1, 其余补 0)
buffer.push_back(true);
while (buffer.size() < 1025) {
buffer.push_back(false);
}
// 3. 计算 31 位机密加权哈希
mt19937 rng(SEED);
uint32_t hash_val = 0;
for (int i = 0; i < 1025; ++i) {
uint32_t w = rng() & MOD_MASK;
if (buffer[i]) {
hash_val = (hash_val + w) & MOD_MASK;
}
}
// 4. 将哈希值追加到缓冲区的最后 31 位，总长 1056
for (int i = 0; i < 31; ++i) {
buffer.push_back((hash_val >> i) & 1);
}
// 5. 提取真正安全的 16 列的索引
vector<int> safe_cols;
for (int i = 0; i < 31; ++i) {
if (!C[i]) safe_cols.push_back(i);
}
// 6. 发送 66 个数据包
int bit_idx = 0;
for (int p = 0; p < 66; ++p) {
vector<bool> packet(31, false);
for (int i = 0; i < 16; ++i) {
packet[safe_cols[i]] = buffer[bit_idx++];
}
send_packet(packet);
}
}
// DFS 状态所需的全局变量（优化速度）
uint32_t check_val[31][16];
int best_chosen[16];
bool found = false;
void dfs(int c, int r, uint32_t current_val, int* chosen) {
if (found) return;
if (r == 16) {
if ((current_val & MOD_MASK) == 0) {
for (int i = 0; i < 16; ++i) best_chosen[i] = chosen[i];
found = true;
}
return;
}
if (31 - c < 16 - r) return; // 剪枝: 剩余列数不足
// 选择当前列 c
chosen[r] = c;
dfs(c + 1, r + 1, (current_val + check_val[c][r]) & MOD_MASK, chosen);
// 不选择当前列 c
dfs(c + 1, r, current_val, chosen);
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
mt19937 rng(SEED);
vector<uint32_t> W(1025);
for (int i = 0; i < 1025; ++i) {
W[i] = rng() & MOD_MASK;
}
// 预计算每列作为第 r 个安全列时的差量贡献
for (int c = 0; c < 31; ++c) {
for (int r = 0; r < 16; ++r) {
uint32_t val = 0;
for (int k = 0; k < 66; ++k) {
int bit_idx = r * 66 + k;
bool b = R[k][c];
if (b) {
if (bit_idx < 1025) {
val = (val + W[bit_idx]) & MOD_MASK;
} else {
int mac_shift = bit_idx - 1025;
uint32_t sub = (1U << mac_shift);
val = (val + MOD_MASK + 1 - sub) & MOD_MASK;
}
}
}
check_val[c][r] = val;
}
}
found = false;
int chosen[16];
dfs(0, 0, 0, chosen);
// 恢复提取出的 1056 位缓冲区
vector<bool> buffer(1056);
int bit_idx = 0;
for (int r = 0; r < 16; ++r) {
int c = best_chosen[r];
for (int k = 0; k < 66; ++k) {
buffer[bit_idx++] = R[k][c];
}
}
// 去掉填充位恢复 M
int original_len = 1025;
while (original_len > 0 && !buffer[original_len - 1]) {
original_len--;
}
original_len--; // 去掉用来分隔的那个 1
vector<bool> M(original_len);
for (int i = 0; i < original_len; ++i) {
M[i] = buffer[i];
}
return M;
}
