Submission #1194545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194545		aykhn	Message (IOI24_message)	C++20	69.71 / 100	439 ms	868 KiB

message

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

using namespace std;

const int B = 3;

int o[8][31] = 
{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30},
{9, 17, 7, 27, 10, 22, 21, 6, 30, 3, 24, 15, 29, 19, 2, 13, 23, 20, 14, 1, 25, 5, 4, 8, 0, 16, 18, 28, 11, 12, 26},
{9, 1, 4, 6, 20, 21, 29, 27, 19, 26, 22, 11, 0, 16, 28, 15, 3, 12, 14, 10, 24, 13, 2, 25, 30, 5, 7, 17, 18, 23, 8},
{22, 24, 26, 1, 9, 14, 27, 23, 21, 5, 3, 0, 4, 30, 18, 11, 19, 28, 15, 29, 7, 20, 13, 10, 8, 2, 17, 16, 6, 12, 25}};

// int o[31] = {9, 17, 7, 27, 10, 22, 21, 6, 30, 3, 24, 15, 29, 19, 2, 13, 23, 20, 14, 1, 25, 5, 4, 8, 0, 16, 18, 28, 11, 12, 26};

int calc(vector<bool> C, int k)
{
  int res = 0;
  vector<int> unlock;
  for (int i = 0; i < 31 && unlock.size() < 16;)
  {
    if (31 - i == 16 - (int)unlock.size())
    {
      for (int j = i; j < 31; j++) unlock.push_back(o[k][j]);
      break;
    }
    vector<bool> v(31, 0);
    int j = 0;
    while (i < 31 && j < unlock.size())
    {
      if (C[o[k][i]] == 0) v[unlock[j]] = 1, unlock.push_back(o[k][i]);
      else v[unlock[j]] = 0;
      i++, j++;
    }
    if ((31 - i) < (16 - (int)unlock.size()) * 2)
    {
      for (int l = i; l < 31; l++) v[o[k][l]] = (C[o[k][i]] == 0);
      if (C[o[k][i]] == 0) unlock.push_back(o[k][i]);
      i++;
    }
    res++;
  }
  return res;
}

void send_message(vector<bool> M, vector<bool> C) 
{
  for (int i = (1 << (B - 1)); i < (1 << B); i++)
  {
    for (int j = 0; j < 31; j++)
    {
      o[i][j] = o[i - (1 << (B - 1))][j];
    }
    reverse(o[i], o[i] + 31);
  }
  int n = M.size();
  int cost[(1 << B)];
  for (int i = 0; i < (1 << B); i++) cost[i] = calc(C, i);
  int k = min_element(cost, cost + (1 << B)) - cost;
  for (int i = 0; i < B; i++) send_packet(vector<bool>(31, k >> i & 1));
  vector<int> unlock;
  for (int i = 0; i < 31 && unlock.size() < 16;)
  {
    if (31 - i == 16 - (int)unlock.size())
    {
      for (int j = i; j < 31; j++) unlock.push_back(o[k][j]);
      break;
    }
    vector<bool> v(31, 0);
    int j = 0;
    while (i < 31 && j < unlock.size())
    {
      if (C[o[k][i]] == 0) v[unlock[j]] = 1, unlock.push_back(o[k][i]);
      else v[unlock[j]] = 0;
      i++, j++;
    }
    if ((31 - i) < (16 - (int)unlock.size()) * 2)
    {
      for (int l = i; l < 31; l++) v[o[k][l]] = (C[o[k][i]] == 0);
      if (C[o[k][i]] == 0) unlock.push_back(o[k][i]);
      i++;
    }
    send_packet(v);
  }
  {
    vector<bool> v(31, 0);
    for (int i = 0; i <= 10; i++) v[unlock[i]] = (n >> i & 1);
    send_packet(v);
  }
  for (int i = 0; i < (n + 15) / 16; i++)
  {
    vector<bool> v(31, 0);
    for (int j = 0; j < 16; j++)
    {
      if (i * 16 + j >= n) break;
      v[unlock[j]] = M[i * 16 + j];
    }
    send_packet(v);
  }
}

vector<bool> receive_message(vector<vector<bool>> R) 
{
  for (int i = (1 << (B - 1)); i < (1 << B); i++)
  {
    for (int j = 0; j < 31; j++)
    {
      o[i][j] = o[i - (1 << (B - 1))][j];
    }
    reverse(o[i], o[i] + 31);
  }
  vector<int> unlock;
  int cur = -1;
  auto nxt = [&]()
  {
    return R[++cur];
  };
  auto get = [&](vector<bool> A)
  {
    int cnt = 0;
    for (auto i : A) cnt += (int)i;
    return cnt >= 16;
  };
  int k = 0;
  for (int i = 0; i < B; i++) k |= (get(nxt()) << i);
  for (int i = 0; i < 31 && unlock.size() < 16;)
  {
    if (31 - i == 16 - (int)unlock.size())
    {
      for (int j = i; j < 31; j++) unlock.push_back(o[k][j]);
      break;
    }
    vector<bool> v = nxt();
    int j = 0;
    while (i < 31 && j < unlock.size())
    {
      if (v[unlock[j]] == 1) unlock.push_back(o[k][i]);
      i++, j++;
    }
    vector<int> un(31, 0);
    for (int j : unlock) un[j] = 1;
    if ((31 - i) < (16 - (int)unlock.size()) * 2)
    {
      int cnt = 0;
      for (int l = i; l < 31; l++) cnt += (int)v[o[k][l]];
      if (cnt >= (16 - (int)unlock.size())) unlock.push_back(o[k][i]);
      i++;
    }
  }
  vector<bool> sz = nxt();
  int n = 0;
  for (int i = 0; i <= 10; i++) 
  {
    if (sz[unlock[i]]) n |= (1 << i);
  }
  vector<bool> res(n, 0);
  for (int i = 0; i < (n + 15) / 16; i++)
  {
    vector<bool> v = nxt();
    for (int j = 0; j < 16; j++)
    {
      if (i * 16 + j >= n) break;
      res[i * 16 + j] = v[unlock[j]];
    }
  }
  return res;
}

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