Submission #1276784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276784		avighna	Message (IOI24_message)	C++20	91.23 / 100	459 ms	852 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 hash = [&](const std::string &data) {
    uint32_t hash = 2166136261;
    for (auto &i : data) {
      hash = (hash ^ i) * 16777619;
    }
    return (hash >> 16) ^ (hash & 0xFFFF);
  };

  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) {
    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, ans_str;
  data.reserve(66 * 31);
  ans_str.reserve(M.size() + 64);
  int cur = 0;
  auto push_bit = [&](bool x) {
    ans_str.push_back(x + '0');
    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, int bits) {
    for (int i = 0; i < bits; ++i) {
      push_bit(x & 1 << i);
    }
  };

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

  push_num(hash(ans_str), 16);

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

  auto send_stream = [&]() {
    std::vector<bool> buf(31);
    for (int i = 0; i < data.size(); i += 31) {
      for (int j = 0; j < 31; ++j) {
        buf[j] = data[i + j] == '1';
      }
      send_packet(buf);
    }
  };
  send_stream();
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  auto hash = [&](const std::string &data) {
    uint32_t hash = 2166136261;
    for (auto &i : data) {
      hash = (hash ^ i) * 16777619;
    }
    return (hash >> 16) ^ (hash & 0xFFFF);
  };

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

  for (int idx = 0; idx < 31; ++idx) {
    int channel = p[idx];
    std::vector<bool> C(31);
    for (int i = 0; i < 31; ++i) {
      C[i] = R[i][channel];
    }
    if (C[channel]) {
      continue;
    }
    if (std::accumulate(C.begin(), C.end(), 0) != 15) {
      continue;
    }

    int cur = 0, j = 0;
    std::string ans_str;
    ans_str.reserve(66 * 31);
    auto recv_bit = [&](bool push) {
      while (C[j]) {
        cur += (j + 1) / 31, j = (j + 1) % 31;
      }
      if (cur < 31 and j == channel) {
        cur += (j + 1) / 31, j = (j + 1) % 31;
      }
      while (C[j]) {
        cur += (j + 1) / 31, j = (j + 1) % 31;
      }
      if (cur >= R.size()) {
        return 0;
      }
      int ans = R[cur][j];
      cur += (j + 1) / 31, j = (j + 1) % 31;
      if (push) {
        ans_str.push_back(ans + '0');
      }
      return ans;
    };

    auto recv_num = [&](int bits, bool hash) {
      int x = 0;
      for (int i = 0; i < bits; ++i) {
        x += recv_bit(!hash) << i;
      }
      return x;
    };

    int size = recv_num(16, false);
    if (size > 1024) {
      continue;
    }
    std::vector<bool> ans(size);
    for (int i = 0; i < size; ++i) {
      ans[i] = recv_bit(true);
    }

    if (hash(ans_str) == recv_num(16, true)) {
      return ans;
    }
  }
  return {}; // will never happen
}

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