Submission #1276639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276639		avighna	Message (IOI24_message)	C++20	53.89 / 100	466 ms	840 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);
  };

  // to get the good average case
  std::mt19937 gen(69420);
  std::vector<int> p(31);
  std::iota(p.begin(), p.end(), 0);
  std::shuffle(p.begin(), p.end(), gen);

  auto send_num_unlocked = [&](int n, int bits) { // assumes receiver only knows first `bits` bits
    std::string msg(31, '0');
    for (int i = 0, j = 0; i < bits; ++i, ++j) {
      while (C[p[j]]) {
        j++;
      }
      msg[p[j]] = !!(n & 1 << i) + '0';
    }
    send(msg);
  };
  auto send_num = [&](int n) {
    send_num_unlocked(n, 16);
  };

  int bits = 0;
  for (int i = 0; i < 31; ++i) {
    if (bits < 2) {
      send(std::string(31, C[p[i]] + '0'));
      bits += !C[p[i]];
    } else {
      int x = 0;
      int n_bits = bits;
      for (int j = 0; j < bits and i + j < 31; ++j) {
        x += int(C[p[i + j]]) << j;
        n_bits += !C[p[i + j]];
      }
      i += bits - 1;
      send_num_unlocked(x, bits);
      bits = n_bits;
    }
  }
  send_num(M.size());
  for (int i = 0; i < M.size(); i += 16) {
    int x = 0;
    for (int j = 0; j < 16 and i + j < M.size(); ++j) {
      x += int(M[i + j]) << j;
    }
    send_num(x);
  }
}

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

  std::vector<bool> C(31, true);

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

  auto recv_num_unlocked = [&](std::vector<bool> P, int bits) {
    int ans = 0;
    for (int i = 0, j = 0; i < bits; ++i, ++j) {
      while (C[p[j]]) {
        j++;
      }
      ans += int(P[p[j]]) << i;
    }
    return ans;
  };
  int cur = 0;

  int bits = 0;
  for (int i = 0; i < 31; ++i) {
    if (bits < 2) {
      C[p[i]] = recv(R[cur++]);
      bits += !C[p[i]];
    } else {
      int x = recv_num_unlocked(R[cur++], bits);
      int n_bits = bits;
      for (int j = 0; j < bits and i + j < 31; ++j) {
        C[p[i + j]] = x & 1 << j;
        n_bits += !C[p[i + j]];
      }
      i += bits - 1;
      bits = n_bits;
    }
  }

  assert(bits == 16);

  auto recv_num = [&](std::vector<bool> P) {
    return recv_num_unlocked(P, 16);
  };

  int size = recv_num(R[cur++]);
  std::vector<bool> M(size);
  for (int i = 0; i < size; i += 16) {
    int x = recv_num(R[cur++]);
    for (int j = 0; j < 16 and i + j < size; ++j) {
      M[i + j] = x & 1 << j;
    }
  }

  return M;
}

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