Submission #1177532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177532		madamadam3	Message (IOI24_message)	C++20	0 / 100	268 ms	848 KiB

message

#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";
}

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 < 4; 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 first = 0;
  // for (int i = 0; i < 4; i++) {
  //   int ones = 0; for (int bit = 0; bit < 31; bit++) ones += R[i][bit];
  //   if (ones < 16) continue;

  //   first |= (1 << i);
  // }

  for (int first = 0; first < 16; first++) {
    vb M;

    // Stage 2: Determine which bits are safe
    vector<int> safe;
    for (int i = 0; i < 31; i++) {
      if (R[i][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][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][safe[bit]]);
      }
    }

    return M;
  }
}

Compilation message (stderr)

message.cpp: In function 'vb receive_message(vvb)':
message.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
   93 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 90