| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1296667 | lucas110550 | Message (IOI24_message) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <algorithm>
#include <string>
#include "message.h"
using std::vector;
using std::string;
// Assumed to be provided elsewhere
void send_packet(const vector<bool>& A);
void send_message(vector<bool> M, vector<bool> C) {
// Find safe indices (positions where C[j] == 0)
vector<int> safe_indices;
for (int j = 0; j < 31; ++j) {
if (C[j] == false) {
safe_indices.push_back(j);
}
}
std::sort(safe_indices.begin(), safe_indices.end());
// First 31 packets: repetition of each bit of C on safe positions
for (int i = 0; i < 31; ++i) {
vector<bool> A(31, false);
for (int idx : safe_indices) {
A[idx] = C[i];
}
send_packet(A);
}
// Encode length S_val of message M using 11 bits
int S_val = static_cast<int>(M.size());
// Convert S_val to binary string without leading zeros
string bin_S;
if (S_val == 0) {
bin_S = "0";
} else {
int tmp = S_val;
while (tmp > 0) {
bin_S.push_back((tmp % 2) + '0');
tmp /= 2;
}
std::reverse(bin_S.begin(), bin_S.end());
}
// Left-pad to 11 bits if needed
if (static_cast<int>(bin_S.size()) < 11) {
bin_S = string(11 - bin_S.size(), '0') + bin_S;
}
// Send S_val encoded on safe_indices[:11]
{
vector<bool> A(31, false);
for (int k = 0; k < 11; ++k) {
A[safe_indices[k]] = (bin_S[k] == '1');
}
send_packet(A);
}
// Split M into chunks of up to 16 bits and send them
int n_chunks = (S_val + 15) / 16;
int start = 0;
for (int chunk_idx = 0; chunk_idx < n_chunks; ++chunk_idx) {
int end = start + 16;
if (end > S_val) {
end = S_val;
}
int L = end - start;
vector<bool> A(31, false);
for (int k = 0; k < L; ++k) {
A[safe_indices[k]] = M[start + k];
}
send_packet(A);
start = end;
}
}
vector<bool> receive_message(vector<vector<bool>> R) {
// Majority-vote decode of C from the first 31 packets
vector<int> received_C(31, 0);
for (int p = 0; p < 31; ++p) {
const vector<bool>& packet = R[p];
int count0 = 0, count1 = 0;
for (bool bit : packet) {
if (bit == false) {
++count0;
} else {
++count1;
}
}
received_C[p] = (count1 > count0) ? 1 : 0;
}
// Compute safe indices from received_C
vector<int> safe_indices;
for (int j = 0; j < 31; ++j) {
if (received_C[j] == 0) {
safe_indices.push_back(j);
}
}
std::sort(safe_indices.begin(), safe_indices.end());
// Decode S_val (message length) from packet R[31] on safe_indices[:11]
const vector<bool>& packet_S = R[31];
vector<int> S_bits;
for (int k = 0; k < 11 && k < static_cast<int>(safe_indices.size()); ++k) {
int j = safe_indices[k];
S_bits.push_back(packet_S[j] ? 1 : 0);
}
int S_val = 0;
for (int b : S_bits) {
S_val = (S_val << 1) | b;
}
int n_chunks = (S_val + 15) / 16;
vector<bool> message;
// Decode chunks from packets R[32 .. 32 + n_chunks - 1]
for (int i = 32; i < 32 + n_chunks && i < static_cast<int>(R.size()); ++i) {
const vector<bool>& packet = R[i];
if (i == 32 + n_chunks - 1) {
// Last chunk may be partial
int L = S_val - 16 * (n_chunks - 1);
for (int k = 0; k < L && k < static_cast<int>(safe_indices.size()); ++k) {
int j = safe_indices[k];
message.push_back(packet[j]);
}
} else {
// Full chunk
for (int idx : safe_indices) {
message.push_back(packet[idx]);
}
}
}
return message;
}