Submission #1246527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246527		madamadam3	Message (IOI24_message)	C++20	100 / 100	414 ms	852 KiB

message

#include "message.h"
#include <bits/stdc++.h>

using namespace std;

using vb = vector<bool>;
using vvb = vector<vb>;

void send_message(vb M, vb C) {
  vector<int> bits; for (int i = 0; i < 31; i++) if (!C[i]) bits.push_back(i);
  int cidx = 0;
  vvb packets(66, vb(31, true));
  for (int i = 0; i < 16; i++) {
    int nxt = (bits[i == 15 ? 0 : i + 1] - bits[i] + 31) % 31;

    for (int j = 0; j < 66; j++) {
      if (j + 1 < nxt) packets[j][bits[i]] = false;
      else if (j + 1 == nxt) packets[j][bits[i]] = true;
      else {
        if (cidx == M.size()) packets[j][bits[i]] = true;
        else if (cidx > M.size()) packets[j][bits[i]] = false;
        else packets[j][bits[i]] = M[cidx];
        cidx++;
      }
    }
  }

  for (auto &el : packets) send_packet(el);
}

vb receive_message(vvb R) {
  vb ans;

  vector<int> nxt(31, -1); 
  vvb info(31, vb());

  for (int i = 0; i < 31; i++) {
    for (int j = 0; j < 66; j++) {
      if (R[j][i] == 1 && nxt[i] == -1) {
        nxt[i] = (i + j + 1) % 31; 
      } else if (nxt[i] != -1) {
        info[i].push_back(R[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;
    }
  }

  for (int i = 0; i < 16; i++) {
    // cout << bits[i] << " ";
    for (int j = 0; j < info[bits[i]].size(); j++) ans.push_back(info[bits[i]][j]);
  }
  // cout << "\n";

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

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