Submission #1276861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276861		avighna	Message (IOI24_message)	C++20	100 / 100	441 ms	816 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) {
  std::vector<int> pos;
  for (int i = 0; i < 31; ++i) {
    if (!C[i]) {
      pos.push_back(i);
    }
  }

  std::vector info(66, std::vector<bool>(31));

  std::vector<int> len(31);
  for (int i = 0; i < 16; ++i) {
    info[(len[pos[i]] = (pos[(i + 1) % 16] - pos[i] + 31) % 31) - 1][pos[i]] = true;
  }

  int i = 0, j = 0;
  auto send = [&](bool bit) {
    while (C[j] or i < len[j]) {
      i += j == 30, j = (j + 1) % 31;
    }
    info[i][j] = bit;
    i += j == 30, j = (j + 1) % 31;
  };

  for (int i = 0; i < 1024 - M.size(); ++i) {
    send(0);
  }
  send(1);
  for (int i = 0; i < M.size(); ++i) {
    send(M[i]);
  }

  for (auto &i : info) {
    send_packet(i);
  }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  std::vector<int> next(31);
  for (int i = 0; i < 31; ++i) {
    int j = 0;
    while (j < 66 and !R[j][i]) {
      j++;
    }
    next[i] = (i + j + 1) % 31;
  }

  std::vector<bool> C(31, true);
  for (int i = 0; i < 31; ++i) {
    int len = 0, u = i;
    std::vector<bool> vis(31);
    while (u != next[u]) {
      if (vis[u]) {
        break;
      }
      vis[u] = true;
      len++, u = next[u];
    }
    if (len == 16 and u == i) {
      while (true) {
        C[u] = false, u = next[u];
        if (u == i) {
          break;
        }
      }
    }
  }
  
  int i = 0, j = 0;
  auto recv = [&]() {
    while (C[j] or i < (next[j] - j + 31) % 31) {
      i += j == 30, j = (j + 1) % 31;
    }
    bool ans = R[i][j];
    i += j == 30, j = (j + 1) % 31;
    return ans;
  };

  std::vector<bool> M;
  for (int i = 0, st = false; i < 1025; ++i) {
    bool bt = recv();
    if (st) {
      M.push_back(bt);
    }
    st |= bt;
  }
  return M;
}

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