| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1267382 | alphabeastmam | Message (IOI24_message) | C++20 | 0 ms | 0 KiB |
#include <iostream>
using namespace std;
// Provided by the grader on the sender side.
extern vector<bool> send_packet(vector<bool> A);
// Helper: write S (<=1024) as 10 bits, MSB-first.
static vector<bool> encode_len10(int S) {
vector<bool> bits(10, false);
for (int i = 9; i >= 0; --i) {
bits[9 - i] = ((S >> i) & 1);
}
return bits;
}
void send_message(vector<bool> M, vector<bool> C) {
// G[i] = 1 means index i is reliable (Cleopatra cannot change it)
vector<bool> G(31, false);
for (int i = 0; i < 31; ++i) G[i] = !C[i];
// Phase 1: send 31 cyclic shifts of G.
// Packet t (0..30) puts G[i] at physical index (i + t) % 31.
for (int t = 0; t < 31; ++t) {
vector<bool> A(31, false);
for (int i = 0; i < 31; ++i) {
int p = (i + t) % 31;
A[p] = G[i];
}
(void)send_packet(A); // discard tainted response; not needed for this strategy
}
// Gather reliable indices in ascending order once (for payload mapping)
vector<int> reliable;
reliable.reserve(16);
for (int i = 0; i < 31; ++i) if (G[i]) reliable.push_back(i);
// Build the payload bitstream: 10-bit length header, then M.
vector<bool> payload = encode_len10((int)M.size());
payload.insert(payload.end(), M.begin(), M.end());
// Phase 2: stream payload using reliable positions (16 bits per packet).
size_t pos = 0;
while (pos < payload.size()) {
vector<bool> A(31, false);
// Fill reliable positions with next up-to-16 bits
for (int j = 0; j < (int)reliable.size(); ++j) {
bool bit = false;
if (pos < payload.size()) {
bit = payload[pos++];
}
A[reliable[j]] = bit;
}
// Controlled positions can be anything (e.g., 0)
(void)send_packet(A);
}
}
#include <bits/stdc++.h>
using namespace std;
// Majority threshold helper (strict > 15 wins over up to 15 corruptions)
static bool majority31(const array<int,31>& onesCount, int i) {
return onesCount[i] > 15; // true if >=16 ones across 31 packets
}
vector<bool> receive_message(vector<vector<bool>> R) {
const int P = (int)R.size();
// First 31 packets are the mask phase
// Undo cyclic shifts and majority-vote per logical index to recover G.
array<int,31> ones{}; ones.fill(0);
for (int t = 0; t < 31; ++t) {
// logical index i is at physical (i + t) % 31
for (int i = 0; i < 31; ++i) {
int phys = (i + t) % 31;
if (R[t][phys]) ++ones[i];
}
}
vector<bool> G(31, false);
for (int i = 0; i < 31; ++i) {
G[i] = (ones[i] > 15); // 16+ ones => reliable
}
// Collect reliable indices in ascending order
vector<int> reliable;
reliable.reserve(16);
for (int i = 0; i < 31; ++i) if (G[i]) reliable.push_back(i);
// Now parse payload packets (packets 31..P-1), 16 bits per packet
vector<bool> bitstream;
for (int t = 31; t < P; ++t) {
// Read reliable positions in the agreed fixed order
for (int idx : reliable) {
bitstream.push_back(R[t][idx]);
}
}
// First 10 bits are the length (MSB-first)
if (bitstream.size() < 10) return {}; // defensive
int S = 0;
for (int i = 0; i < 10; ++i) {
S = (S << 1) | (bitstream[i] ? 1 : 0);
}
// Next S bits are the message
vector<bool> M;
M.reserve(S);
for (int i = 10; i < 10 + S && i < (int)bitstream.size(); ++i) {
M.push_back(bitstream[i]);
}
return M;
}