#include "message.h"
#include <bits/stdc++.h>
using namespace std;
const int B = 4, REV = 0;
int o[(1 << B)][31] =
{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30},
{9, 17, 7, 27, 10, 22, 21, 6, 30, 3, 24, 15, 29, 19, 2, 13, 23, 20, 14, 1, 25, 5, 4, 8, 0, 16, 18, 28, 11, 12, 26},
{30, 3, 28, 4, 10, 16, 11, 18, 8, 7, 12, 17, 15, 20, 19, 21, 23, 6, 9, 29, 25, 0, 14, 1, 26, 22, 2, 13, 5, 24, 27},
{22, 24, 26, 1, 9, 14, 27, 23, 21, 5, 3, 0, 4, 30, 18, 11, 19, 28, 15, 29, 7, 20, 13, 10, 8, 2, 17, 16, 6, 12, 25},
{24, 4, 22, 12, 9, 5, 11, 15, 19, 14, 20, 16, 2, 13, 28, 7, 17, 6, 8, 29, 18, 10, 1, 3, 23, 30, 26, 0, 27, 25, 21},
{27, 12, 18, 25, 2, 23, 0, 17, 7, 26, 24, 13, 29, 9, 19, 4, 16, 10, 28, 15, 30, 8, 5, 21, 11, 14, 22, 1, 6, 20, 3},
{11, 6, 3, 21, 0, 15, 13, 26, 29, 16, 19, 18, 14, 7, 8, 27, 10, 30, 9, 2, 12, 4, 17, 23, 22, 28, 24, 25, 1, 20, 5},
{28, 7, 1, 26, 10, 19, 15, 2, 24, 0, 9, 18, 8, 30, 14, 17, 13, 20, 4, 27, 11, 3, 22, 6, 12, 16, 21, 29, 23, 25, 5},
{18, 6, 28, 10, 17, 8, 5, 16, 11, 14, 9, 25, 12, 30, 4, 1, 3, 22, 24, 20, 27, 19, 0, 7, 15, 26, 21, 13, 29, 23, 2},
{18, 9, 11, 12, 23, 25, 24, 3, 28, 27, 4, 14, 15, 26, 30, 29, 0, 5, 19, 17, 22, 1, 16, 10, 8, 20, 21, 2, 7, 6, 13},
{26, 7, 19, 20, 13, 10, 23, 2, 25, 15, 22, 14, 29, 12, 28, 4, 9, 0, 24, 30, 6, 27, 17, 21, 11, 16, 5, 8, 1, 3, 18},
{7, 17, 29, 28, 15, 12, 8, 22, 23, 3, 4, 13, 0, 21, 18, 19, 5, 6, 1, 14, 9, 16, 26, 24, 25, 2, 20, 10, 11, 30, 27},
{0, 21, 27, 20, 26, 8, 15, 19, 6, 24, 29, 3, 30, 16, 22, 1, 7, 18, 4, 28, 12, 23, 9, 17, 5, 2, 10, 13, 11, 14, 25},
{12, 1, 11, 4, 5, 17, 3, 21, 28, 22, 20, 30, 2, 18, 16, 29, 27, 23, 13, 10, 14, 19, 26, 15, 6, 7, 8, 25, 24, 9, 0},
{13, 19, 14, 25, 18, 20, 22, 21, 24, 4, 28, 10, 1, 26, 8, 5, 0, 6, 16, 12, 29, 11, 30, 23, 2, 7, 27, 15, 17, 3, 9},
{12, 20, 3, 11, 5, 2, 28, 23, 22, 17, 30, 4, 27, 14, 9, 25, 26, 0, 18, 6, 15, 29, 8, 19, 10, 16, 13, 1, 21, 7, 24}};
// int o[31] = {9, 17, 7, 27, 10, 22, 21, 6, 30, 3, 24, 15, 29, 19, 2, 13, 23, 20, 14, 1, 25, 5, 4, 8, 0, 16, 18, 28, 11, 12, 26};
int calc(vector<bool> C, int k)
{
int res = 0;
vector<int> unlock;
for (int i = 0; i < 31 && unlock.size() < 16;)
{
if (31 - i == 16 - (int)unlock.size())
{
for (int j = i; j < 31; j++) unlock.push_back(o[k][j]);
break;
}
vector<bool> v(31, 0);
int j = 0;
while (i < 31 && j < unlock.size())
{
if (C[o[k][i]] == 0) v[unlock[j]] = 1, unlock.push_back(o[k][i]);
else v[unlock[j]] = 0;
i++, j++;
}
if ((31 - i) < (16 - (int)unlock.size()) * 2)
{
for (int l = i; l < 31; l++) v[o[k][l]] = (C[o[k][i]] == 0);
if (C[o[k][i]] == 0) unlock.push_back(o[k][i]);
i++;
}
res++;
}
return res;
}
void send_message(vector<bool> M, vector<bool> C)
{
for (int i = (1 << (B - 1)); REV && i < (1 << B); i++)
{
for (int j = 0; j < 31; j++)
{
o[i][j] = o[i - (1 << (B - 1))][j];
}
reverse(o[i], o[i] + 31);
}
int n = M.size();
int cost[(1 << B)];
for (int i = 0; i < (1 << B); i++) cost[i] = calc(C, i);
int k = min_element(cost, cost + (1 << B)) - cost;
for (int i = 0; i < B; i++) send_packet(vector<bool>(31, k >> i & 1));
vector<int> unlock;
for (int i = 0; i < 31 && unlock.size() < 16;)
{
if (31 - i == 16 - (int)unlock.size())
{
for (int j = i; j < 31; j++) unlock.push_back(o[k][j]);
break;
}
vector<bool> v(31, 0);
int j = 0;
while (i < 31 && j < unlock.size())
{
if (C[o[k][i]] == 0) v[unlock[j]] = 1, unlock.push_back(o[k][i]);
else v[unlock[j]] = 0;
i++, j++;
}
if ((31 - i) < (16 - (int)unlock.size()) * 2)
{
for (int l = i; l < 31; l++) v[o[k][l]] = (C[o[k][i]] == 0);
if (C[o[k][i]] == 0) unlock.push_back(o[k][i]);
i++;
}
send_packet(v);
}
{
vector<bool> v(31, 0);
for (int i = 0; i <= 10; i++) v[unlock[i]] = (n >> i & 1);
send_packet(v);
}
for (int i = 0; i < (n + 15) / 16; i++)
{
vector<bool> v(31, 0);
for (int j = 0; j < 16; j++)
{
if (i * 16 + j >= n) break;
v[unlock[j]] = M[i * 16 + j];
}
send_packet(v);
}
}
vector<bool> receive_message(vector<vector<bool>> R)
{
for (int i = (1 << (B - 1)); REV && i < (1 << B); i++)
{
for (int j = 0; j < 31; j++)
{
o[i][j] = o[i - (1 << (B - 1))][j];
}
reverse(o[i], o[i] + 31);
}
vector<int> unlock;
int cur = -1;
auto nxt = [&]()
{
return R[++cur];
};
auto get = [&](vector<bool> A)
{
int cnt = 0;
for (auto i : A) cnt += (int)i;
return cnt >= 16;
};
int k = 0;
for (int i = 0; i < B; i++) k |= (get(nxt()) << i);
for (int i = 0; i < 31 && unlock.size() < 16;)
{
if (31 - i == 16 - (int)unlock.size())
{
for (int j = i; j < 31; j++) unlock.push_back(o[k][j]);
break;
}
vector<bool> v = nxt();
int j = 0;
while (i < 31 && j < unlock.size())
{
if (v[unlock[j]] == 1) unlock.push_back(o[k][i]);
i++, j++;
}
vector<int> un(31, 0);
for (int j : unlock) un[j] = 1;
if ((31 - i) < (16 - (int)unlock.size()) * 2)
{
int cnt = 0;
for (int l = i; l < 31; l++) cnt += (int)v[o[k][l]];
if (cnt >= (16 - (int)unlock.size())) unlock.push_back(o[k][i]);
i++;
}
}
vector<bool> sz = nxt();
int n = 0;
for (int i = 0; i <= 10; i++)
{
if (sz[unlock[i]]) n |= (1 << i);
}
vector<bool> res(n, 0);
for (int i = 0; i < (n + 15) / 16; i++)
{
vector<bool> v = nxt();
for (int j = 0; j < 16; j++)
{
if (i * 16 + j >= n) break;
res[i * 16 + j] = v[unlock[j]];
}
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |