Submission #1109036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109036		nicksms	Message (IOI24_message)	C++17	100 / 100	2878 ms	1088 KiB

message

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

void send_message(std::vector<bool> M, std::vector<bool> C) {
  M.push_back(M.back());
  while (M.size() < 1025) M.push_back(!M.back());
  std::vector<std::vector<bool>> messages(16);
  std::vector<int> k(16);
  int c = 0, t = 0;
  for (int i = 0; i < 31; i++) {if (C[i]) c++; else k[t++]=c,c=0;}
  k[0] += c;
  int ind = 0;
  for (int i = 0; i < 16; i++) {
    while (k[i]--) messages[i].push_back(true);
    messages[i].push_back(false);
    while (messages[i].size() < 66) messages[i].push_back(M[ind++]);
    // std::cout << i << " " << ind << std::endl;
  }
  for (int i = 0; i < 66; i++) {
    std::vector<bool> tmp(31);
    int k = 0;
    for (int j = 0; j < 31; j++)
      if (!C[j]) tmp[j]=messages[k++][i];
    // for (int i : tmp) std::cout << i << " ";
    // std::cout << std::endl;
    send_packet(tmp);
  }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
  assert(R.size() == 66);
  std::vector<int> k(31);
  std::vector<bool> C(31,1);
  for (int i = 0; i < 66; i++)
    for (int j = 0; j < 31; j++)
      if (k[j] == i && R[i][j]) k[j]++;
  for (int j = 0; j < 31; j++) {
    int h = 0;
    int cur = j;
    while (h < 100 && (!h || cur != j)) {
      h++;
      cur = (3100 + cur - k[cur]-1) % 31;
    }
    if (h == 16) C[j]=0;
    // std::cout << j << " " << h << " " << k[j] << std::endl;
  }
  // for (int i : C) std::cout << i << " ";
  // std::cout << std::endl;
  std::vector<bool> M;
  for (int i = 0; i < 31; i++) {
    if (C[i]) continue;
    bool seen = false;
    for (int j = 0; j < 66; j++) {
      if (seen) M.push_back(R[j][i]);
      else if (!R[j][i]) seen=true;
    }
  }
  while (M[M.size()-1] != M[M.size()-2]) M.pop_back();
  M.pop_back();
  return M;
}

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