| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1291790 | lucas110550 | Message (IOI24_message) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <array>
#include <algorithm>
#include <cstdint>
#include <cassert>
#include "message.h"
using Packet = std::array<int, 31>;
void send_message(const std::vector<int>& M, const std::array<int, 31>& C) {
const int S = static_cast<int>(M.size());
const int P = (S + 15) / 16; // Number of message packets
// fixed_indices = sorted([i for i in range(31) if C[i] == 0])
std::vector<int> fixed_indices;
fixed_indices.reserve(31);
for (int i = 0; i < 31; ++i) {
if (C[i] == 0) fixed_indices.push_back(i);
}
std::sort(fixed_indices.begin(), fixed_indices.end());
assert(static_cast<int>(fixed_indices.size()) >= 16 && "Need at least 16 fixed positions");
// Send P data packets
for (int k = 0; k < P; ++k) {
Packet packet{}; // zero-initialized
const int start = 16 * k;
for (int j = 0; j < 16; ++j) {
const int pos = start + j;
packet[ fixed_indices[j] ] = (pos < S) ? M[pos] : 0;
}
send_packet(packet);
}
// Send extra packet 0
{
Packet packet0{};
for (int j = 0; j < 11; ++j) {
int bit = (S >> j) & 1;
packet0[ fixed_indices[j] ] = bit;
}
for (int j = 11; j < 16; ++j) {
packet0[ fixed_indices[j] ] = 1;
}
send_packet(packet0);
}
// Send extra packet 1
{
Packet packet1{};
for (int j = 0; j < 11; ++j) {
int bit = (S >> j) & 1;
packet1[ fixed_indices[j] ] = 1 - bit;
}
for (int j = 11; j < 16; ++j) {
packet1[ fixed_indices[j] ] = 0;
}
send_packet(packet1);
}
}
std::vector<int> receive_message(const std::vector<Packet>& R) {
std::vector<int> M;
if (R.size() < 2) return M; // not enough packets
const Packet& extra0 = R[R.size() - 2];
const Packet& extra1 = R[R.size() - 1];
// fixed_indices: positions where extra0 and extra1 differ
std::vector<int> fixed_indices;
fixed_indices.reserve(31);
for (int i = 0; i < 31; ++i) {
if (extra0[i] != extra1[i]) fixed_indices.push_back(i);
}
std::sort(fixed_indices.begin(), fixed_indices.end());
// Recover S (message length)
int S = 0;
for (int j = 0; j < 11; ++j) {
if (j < static_cast<int>(fixed_indices.size())) {
int bit = extra0[ fixed_indices[j] ];
S |= ((bit & 1) << j);
} else {
break;
}
}
const int P = (S + 15) / 16;
M.reserve(S);
for (int k = 0; k < P; ++k) {
if (k >= static_cast<int>(R.size())) break; // not enough packets provided
const Packet& packet = R[k];
const int start = 16 * k;
if (start >= S) break;
for (int j = 0; j < 16; ++j) {
const int pos = start + j;
if (pos >= S) break;
// Assumes fixed_indices has at least 16 entries (as produced by sender)
int bit = packet[ fixed_indices[j] ];
M.push_back(bit);
}
}
return M;
}