| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1291791 | 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;
}
If you prefer std::vector<int> for C instead of std::array<int,31>, just change the parameter type and keep the size check (assert(C.size()==31)), everything else stays the same.
2/2
你说：
message.cpp: In function 'void send_message(const std::vector<int>&, const std::array<int, 31>&)':
message.cpp:32:21: error: could not convert 'packet' from 'Packet' {aka 'std::array<int, 31>'} to 'std::vector<bool>'
32 | send_packet(packet);
| ^~~~~~
| |
| Packet {aka std::array<int, 31>}
message.cpp:45:21: error: could not convert 'packet0' from 'Packet' {aka 'std::array<int, 31>'} to 'std::vector<bool>'
45 | send_packet(packet0);
| ^~~~~~~
| |
| Packet {aka std::array<int, 31>}
message.cpp:58:21: error: could not convert 'packet1' from 'Packet' {aka 'std::array<int, 31>'} to 'std::vector<bool>'
58 | send_packet(packet1);
| ^~~~~~~
| |
| Packet {aka std::array<int, 31>}
ChatGPT 说：
Your send_packet takes a std::vector<bool>, but my code used std::array<int,31>. Here’s a drop-in version that uses std::vector<bool> everywhere.
cpp
复制代码
#include <vector>
#include <array>
#include <algorithm>
#include <cassert>
using Packet = std::vector<bool>;
// Provided by you elsewhere:
extern void send_packet(const std::vector<bool>& packet);
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
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(31, false); // all zeros
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) : false;
}
send_packet(packet);
}
// Send extra packet 0
{
Packet packet0(31, false);
for (int j = 0; j < 11; ++j) {
bool bit = ((S >> j) & 1) != 0;
packet0[ fixed_indices[j] ] = bit;
}
for (int j = 11; j < 16; ++j) {
packet0[ fixed_indices[j] ] = true;
}
send_packet(packet0);
}
// Send extra packet 1
{
Packet packet1(31, false);
for (int j = 0; j < 11; ++j) {
bool bit = ((S >> j) & 1) != 0;
packet1[ fixed_indices[j] ] = !bit;
}
for (int j = 11; j < 16; ++j) {
packet1[ fixed_indices[j] ] = false;
}
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];
assert(extra0.size() == 31 && extra1.size() == 31);
// 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())) {
bool bit = extra0[ fixed_indices[j] ];
S |= (static_cast<int>(bit) << 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];
assert(packet.size() == 31);
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)
bool bit = packet[ fixed_indices[j] ];
M.push_back(bit ? 1 : 0);
}
}
return M;
}