Submission #1246510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246510		madamadam3	Message (IOI24_message)	C++20	81.45 / 100	404 ms	852 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) {
  vector<int> bits; for (int i = 0; i < 31; i++) if (!C[i]) bits.push_back(i);
  for (int i = 0; i < 5; i++) {
    vb to_send(31);
    for (int bit = 0; bit < 16; bit++) {
      int nxt = bit == 15 ? 0 : bit + 1;
      to_send[bits[bit]] = bits[nxt] & (1 << i);
    }
    send_packet(to_send);
  }

  int cidx = 0;
  for (int i = 5; i < 70; i++) {
    vb packet(31);
    for (int j = 0; j < 16; j++) {
      if (cidx == M.size()) packet[bits[j]] = 1;
      else if (cidx > M.size()) packet[bits[j]] = 0;
      else packet[bits[j]] = M[cidx];

      cidx++;
    }

    send_packet(packet);
  }
}

vb receive_message(vvb R) {
  vector<int> nxt(31, 0);
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 31; j++) {
      nxt[j] |= R[i][j] << i;
    }
  }

  vector<int> bits;
  for (int i = 0; i < 31; i++) {
    int cur = i; vector<int> trial;

    while (trial.size() < 16 && !count(trial.begin(), trial.end(), cur) && cur != 31) {
      trial.push_back(cur);
      cur = nxt[cur];
    }

    if (trial.size() == 16 && nxt[trial.back()] == i) {
      bits = trial; break;
    }
  }

  vb ans;
  for (int i = 5; i < R.size(); i++) {
    for (int j = 0; j < 16; j++) {
      ans.push_back(R[i][bits[j]]);
    }
  }

  while (!ans.back()) ans.pop_back();
  ans.pop_back();
  return ans;
}

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