Submission #1177536

#TimeUsernameProblemLanguageResultExecution timeMemory
1177536madamadam3메시지 (IOI24_message)C++20
79.64 / 100
416 ms848 KiB
#include "message.h" #include <bits/stdc++.h> using namespace std; using vb = vector<bool>; using vvb = vector<vb>; const vb ZERO(31, false); const vb ONE(31, true); void trace_vb(vb inp) { for (int i = 0; i < (int) inp.size(); i++) { cout << (inp[i] ? "1 " : "0 "); } cout << "\n"; } const int NUM_FIRST_BITS = 4; void send_message(vb M, vb C) { // Stage 1: broadcast the location of the first bit (4 packets) int first = 0; while (C[first]) first++; for (int i = 0; i < NUM_FIRST_BITS; i++) { if (first & (1 << i)) send_packet(ONE); else send_packet(ZERO); } // Stage 2: broadcast the information vector<int> mask; for (int i = 0; i < 31; i++) if (!C[i]) mask.push_back(i); int S = (int) M.size(), midx = 0; int packets = S <= 64 ? 53 : 67; for (int i = 0; i < packets; i++) { vb packet(31, false); if (i < 31) { packet[first] = !C[i]; } else if (i < 42) { int bit = i - 31; packet[first] = S & (1 << bit); } if (midx < S) { int start = i < 42 ? 1 : 0; for (int off = start; off < 16 && midx < S; off++) { packet[mask[off]] = M[midx++]; } } send_packet(packet); } } vb receive_message(vvb R) { // vb M; // Stage 1: Receive index of first bit int rBits = 0; for (int i = 0; i < NUM_FIRST_BITS; i++) { int ones = 0; for (int bit = 0; bit < 31; bit++) ones += R[i][bit]; if (ones < 16) continue; rBits |= (1 << i); } for (int first = 0; first < 16; first++) { if ((first & rBits) != rBits) continue; vb M; // Stage 2: Determine which bits are safe vector<int> safe; for (int i = 0; i < 31; i++) { if (R[i + NUM_FIRST_BITS][first]) safe.push_back(i); } if ((int) safe.size() != 16) continue; // Stage 3: Determine the length of the message int length = 0; for (int i = 0; i < 11; i++) { if (R[i + 31 + NUM_FIRST_BITS][first]) length |= (1 << i); } // Stage 4: Determine message contents int packets = length <= 64 ? 53 : 67; for (int i = 0; i < packets; i++) { int start = i < 42 ? 1 : 0; for (int bit = start; bit < 16 && (int) M.size() < length; bit++) { M.push_back(R[i + NUM_FIRST_BITS][safe[bit]]); } } return M; } return vb(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...