#include <vector>
using namespace std;
// 选手不需要实现该函数，仅作声明
vector<bool> send_packet(vector<bool> A);
// 生成一个伪随机的映射，避免被自适应评测机抓到固定规律
void get_mapping(int map_k[31], int map_r[31]) {
int counts[16] = {0};
for (int i = 0; i < 31; i++) {
// 使用简单的哈希步长打乱 C 的 31 个比特放在哪个安全列
map_k[i] = (i * 13) % 16;
while (counts[map_k[i]] == 2) {
map_k[i] = (map_k[i] + 1) % 16;
}
// map_r 代表放在第 65 还是 66 个数据包 (索引为 65 和 66)
map_r[i] = 65 + counts[map_k[i]];
counts[map_k[i]]++;
}
}
// Aisha 的发送策略
void send_message(vector<bool> M, vector<bool> C) {
int S = M.size();
vector<bool> P;
// 1. 将长度 S 编码进前 11 个比特
for (int i = 0; i < 11; i++) {
P.push_back((S >> i) & 1);
}
// 2. 压入实际的消息 M
for (int i = 0; i < S; i++) {
P.push_back(M[i]);
}
// 3. 补齐到 1040 个比特 (16 列 * 每列前 65 个比特用于存数据 = 1040)
while (P.size() < 1040) {
P.push_back(0);
}
// 找出 16 个安全列
vector<int> S_col;
for (int i = 0; i < 31; i++) {
if (!C[i]) S_col.push_back(i);
}
// 准备发送矩阵 data[col][packet_index]
// 总共发送 67 个包，索引 0~66
vector<vector<bool>> data(31, vector<bool>(67, 0));
// 将 1040 个有效数据分配到 16 个安全列的前 65 个包中
for (int k = 0; k < 16; k++) {
int col = S_col[k];
for (int i = 0; i < 65; i++) {
data[col][i] = P[k * 65 + i];
}
}
// 将 31 个比特的 C 分布式储存在 16 个安全列的最后 2 个包中
int map_k[31], map_r[31];
get_mapping(map_k, map_r);
for (int i = 0; i < 31; i++) {
int target_col = S_col[map_k[i]];
data[target_col][map_r[i]] = C[i];
}
// 发送这 67 个数据包
for (int p = 0; p < 67; p++) {
vector<bool> A(31);
for (int i = 0; i < 31; i++) {
A[i] = data[i][p]; // Cleopatra 会改写其中 15 个，不用理会
}
send_packet(A);
}
}
// Basma 的接收策略
vector<bool> receive_message(vector<vector<bool>> R) {
int map_k[31], map_r[31];
get_mapping(map_k, map_r);
vector<bool> best_C;
// 利用 DFS 剪枝爆破出那唯一的 16 个安全列组合
auto dfs = [&](auto& self, int col, int k, vector<int>& current_C) -> bool {
// 搜索到底部，且正好找齐了 16 个安全列
if (col == 31) {
if (k == 16) {
best_C = vector<bool>(current_C.begin(), current_C.end());
return true;
}
return false;
}
// 分支 1：假设当前列是【被篡改列】
// 剩余的列必须足以凑齐 16 个安全列
if (col - k < 15) {
if (current_C[col] == -1 || current_C[col] == 1) { // 没有矛盾
int old = current_C[col];
current_C[col] = 1;
if (self(self, col + 1, k, current_C)) return true;
current_C[col] = old; // 回溯
}
}
// 分支 2：假设当前列是【安全列】
if (k < 16) {
if (current_C[col] == -1 || current_C[col] == 0) { // 必须等于 0 (安全)
vector<int> rollback_indices;
vector<int> rollback_values;
bool ok = true;
auto set_val = [&](int idx, int val) {
if (current_C[idx] != -1 && current_C[idx] != val) {
ok = false; // 出现自相矛盾！立刻剪枝
} else if (current_C[idx] == -1) {
rollback_indices.push_back(idx);
rollback_values.push_back(-1);
current_C[idx] = val;
}
};
// 本列必定是 0
set_val(col, 0);
// 当前列作为第 k 个安全列，它最后两个包必须和 C 的相关位一致
for (int i = 0; i < 31; i++) {
if (map_k[i] == k) {
set_val(i, R[map_r[i]][col]);
}
}
// 如果毫无矛盾，继续深搜
if (ok) {
if (self(self, col + 1, k + 1, current_C)) return true;
}
// 还原现场 (回溯)
for (size_t i = 0; i < rollback_indices.size(); i++) {
current_C[rollback_indices[i]] = rollback_values[i];
}
}
}
return false;
};
// 初始化时所有位置未知 (-1)
vector<int> current_C(31, -1);
dfs(dfs, 0, 0, current_C);
// 根据最佳推导结果提取 S_col
vector<int> S_col;
for (int i = 0; i < 31; i++) {
if (!best_C[i]) S_col.push_back(i);
}
// 提取所有数据
vector<bool> P(1040);
for (int k = 0; k < 16; k++) {
int col = S_col[k];
for (int i = 0; i < 65; i++) {
P[k * 65 + i] = R[i][col];
}
}
// 前 11 个比特解码出消息的原始长度 S
int S = 0;
for (int i = 0; i < 11; i++) {
if (P[i]) S |= (1 << i);
}
// 截取 S 长度的原始消息
vector<bool> M(S);
for (int i = 0; i < S; i++) {
M[i] = P[11 + i];
}
return M;
}
