Submission #1276774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276774		avighna	Message (IOI24_message)	C++20	66.72 / 100	476 ms	824 KiB

message

#include <bits/stdc++.h>

std::vector<bool> send_packet(std::vector<bool> A);

void send_message(std::vector<bool> M, std::vector<bool> C) {
  auto send = [&](const std::string &s) {
    std::vector<bool> a(s.length());
    for (int i = 0; i < s.length(); ++i) {
      a[i] = s[i] == '1';
    }
    send_packet(a);
  };

  std::mt19937 gen(69420);
  std::vector<int> p(31);
  std::iota(p.begin(), p.end(), 0);
  std::shuffle(p.begin(), p.end(), gen);

  int bits = 0, i = 0;
  while (bits == 0) {
    send(std::string(31, C[p[i]] + '0'));
    bits += !C[p[i]];
    i += !bits;
  }
  int channel = p[i];

  std::string c_str(31, '0');
  for (int i = 0; i < 31; ++i) {
    c_str[i] = C[i] + '0';
  }

  std::string data;
  int cur = 0;
  auto push_bit = [&](bool x) {
    while (C[cur % 31]) {
      data.push_back('0'), cur++;
    }
    if (cur / 31 < 31 and cur % 31 == channel) {
      data.push_back(c_str[cur / 31]), cur++;
    }
    while (C[cur % 31]) {
      data.push_back('0'), cur++;
    }
    data.push_back(x + '0'), cur++;
  };

  auto push_num = [&](int x) {
    for (int i = 0; i < 16; ++i) {
      push_bit(x & 1 << i);
    }
  };

  push_num(M.size());
  for (int i = 0; i < M.size(); ++i) {
    push_bit(M[i]);
  }

  while (cur / 31 < 31) {
    push_bit(0);
  }
  while (cur % 31 != 0) {
    data.push_back('0'), cur++;
  }

  auto send_stream = [&]() {
    for (int i = 0; i < data.length(); i += 31) {
      send(data.substr(i, 31));
    }
  };
  send_stream();
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  int cur = 0;
  auto recv = [&]() {
    auto P = R[cur++];
    int o = 0, z = 0;
    for (bool i : P) {
      o += i, z += !i;
    }
    return o > z;
  };

  std::mt19937 gen(69420);
  std::vector<int> p(31);
  std::iota(p.begin(), p.end(), 0);
  std::shuffle(p.begin(), p.end(), gen);

  int i = 0;
  while (recv()) {
    i++;
  }
  int channel = p[i];

  std::vector<bool> C(31);
  for (int i = 0; i < 31; ++i) {
    C[i] = R[cur + i][channel];
  }

  int j = 0;
  int base_cur = cur;
  auto recv_bit = [&]() {
    while (C[j]) {
      cur += (j + 1) / 31, j = (j + 1) % 31;
    }
    if ((cur - base_cur) < 31 and j == channel) {
      cur += (j + 1) / 31, j = (j + 1) % 31;
    }
    while (C[j]) {
      cur += (j + 1) / 31, j = (j + 1) % 31;
    }
    int ans = R[cur][j];
    cur += (j + 1) / 31, j = (j + 1) % 31;
    return ans;
  };

  auto recv_num = [&]() {
    int x = 0;
    for (int i = 0; i < 16; ++i) {
      x += recv_bit() << i;
    }
    return x;
  };

  int size = recv_num();
  std::vector<bool> ans(size);
  for (int i = 0; i < size; ++i) {
    ans[i] = recv_bit();
  }
  return ans;
}

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