Submission #258629

#	Time	Username	Problem	Language	Result	Execution time	Memory
258629		ipaljak	Data Transfer (IOI19_transfer)	C++14	100 / 100	752 ms	2676 KiB

transfer

#include "transfer.h"

#include <cassert>
#include <cstdio>

std::vector<int> get_attachment(std::vector<int> source) {
  int r = 0, n = (int) source.size();
  while ((1 << r) < n + r + 1) ++r;
  std::vector<int> message(n + r);
  int ptr = 0;
  for (int i = 0; i < (int) message.size(); ++i)
    if (__builtin_popcount(i + 1) != 1)
      message[i] = source[ptr++];
    else
      message[i] = 0;
  assert(ptr == n);

  for (int i = 0; i < (int) message.size(); ++i) {
    if (__builtin_popcount(i + 1) == 1) continue;
    for (int j = 0; j <= r; ++j)
      if ((i + 1) & (1 << j))
        message[(1 << j) - 1] ^= message[i];
  }

  std::vector<int> attach;
  for (int i = 0; i < (int) message.size(); ++i)
    if (__builtin_popcount(i + 1) == 1)
      attach.push_back(message[i]);

  return attach;
}

std::vector<int> retrieve(std::vector<int> _data) {
  int r = 0, n = (int) _data.size();
  while ((1 << r) < n + r + 1) { ++r; --n; }
  assert(n + r == (int) _data.size());

  std::vector<int> data(n + r);
  int ptr = 0;
  for (int i = 0; i < (int) _data.size(); ++i)
    if (__builtin_popcount(i + 1) != 1) data[i] = _data[ptr++];
  for (int i = 0; i < (int) _data.size(); ++i)
    if (__builtin_popcount(i + 1) == 1) data[i] = _data[ptr++];

  int fix = 0;
  for (int i = 0; i < (int) data.size(); ++i) {
    if (__builtin_popcount(i + 1) == 1) continue;
    for (int j = 0; (1 << j) <= i + 1; ++j) {
      if ((i + 1) & (1 << j))
        data[(1 << j) - 1] ^= data[i];
    }
  }

  for (int i = 0; i < (int) data.size(); ++i)
    if (__builtin_popcount(i + 1) == 1 && data[i] == 1)
      fix += i + 1;
  if (fix != 0)
    data[fix - 1] ^= 1;

  std::vector<int> message;
  for (int i = 0; i < (int) data.size(); ++i)
    if (__builtin_popcount(i + 1) != 1)
      message.push_back(data[i]);
  return message;
}

• Subtask 1: 60 / 60
• Subtask 2: 40 / 40