Submission #1105028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105028		flashmt	Message (IOI24_message)	C++17	83.31 / 100	1317 ms	1092 KiB

message

// 70 queries

#include "message.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int BIT = 31;
const int GOOD = 16;
const int FIRST = 4;
const int SECOND = 37;
const int BOUND = 400;

void send_message(std::vector<bool> m, std::vector<bool> c) {
  for (int i = 0; i < BIT; i++)
    c[i] = !c[i];

  int start = 0;
  while (!c[start])
    start++;

  vector<int> good;
  for (int i = 0; i < BIT; i++)
    if (c[(start + i) % BIT])
      good.push_back((start + i) % BIT);

  for (int i = 0; i < FIRST; i++)
    send_packet(vector<bool>(BIT, start >> i & 1));

  bool lastBit = m.back();
  int len = size(m);
  reverse(begin(m), end(m));
  auto pop = [&]()
  {
    if (empty(m))
      return !lastBit;
    bool res = m.back();
    m.pop_back();
    return res;
  };

  for (int i = 1; i < BIT - 1; i++)
  {
    vector<bool> packet(BIT);
    packet[start] = c[(start + i) % BIT];
    for (int j = 1; j < GOOD; j++)
      packet[good[j]] = pop();
    send_packet(packet);
  }

  if (len > BOUND)
    for (int i = 0; i < SECOND; i++)
    {
      vector<bool> packet(BIT);
      for (int j : good)
        packet[j] = pop();
      send_packet(packet);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> a) {
  int start = 0;
  for (int i = 0; i < FIRST; i++)
  {
    int sum = 0;
    for (auto x : a[i])
      if (x) sum++;
      else sum--;
    if (sum > 0)
      start |= 1 << i;
  }

  vector<int> good = {start};
  for (int i = 1; i < BIT - 1; i++)
    if (a[FIRST + i - 1][start])
      good.push_back((start + i) % BIT);

  if (size(good) < GOOD)
    good.push_back((start + BIT - 1) % BIT);

  vector<bool> ans;
  for (int i = 0; i < BIT - 2; i++)
    for (int j = 1; j < GOOD; j++)
      ans.push_back(a[FIRST + i][good[j]]);

  for (int i = FIRST + BIT - 2; i < size(a); i++)
    for (int j : good)
      ans.push_back(a[i][j]);

  int lastBit = ans.back();
  while (ans.back() == lastBit)
    ans.pop_back();
  return ans;
}

Compilation message (stderr)

message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:89:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int i = FIRST + BIT - 2; i < size(a); i++)
      |                                 ~~^~~~~~~~~

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