oj.uz

Submission #258629

# Submission time Handle Problem Language Result Execution time Memory
258629 2020-08-06T09:31:16 Z ipaljak Data Transfer (IOI19_transfer) C++14
100 / 100
 752 ms 2676 KB 
#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.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1136 KB Output is correct
2 Correct 13 ms 1152 KB Output is correct
3 Correct 13 ms 1032 KB Output is correct
4 Correct 13 ms 1144 KB Output is correct
5 Correct 13 ms 912 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct
7 Correct 13 ms 912 KB Output is correct
8 Correct 13 ms 1148 KB Output is correct
9 Correct 13 ms 1040 KB Output is correct
10 Correct 13 ms 1148 KB Output is correct
11 Correct 13 ms 1148 KB Output is correct
12 Correct 13 ms 1156 KB Output is correct
13 Correct 13 ms 1040 KB Output is correct
14 Correct 13 ms 932 KB Output is correct
15 Correct 13 ms 1408 KB Output is correct
16 Correct 13 ms 1260 KB Output is correct
17 Correct 13 ms 1148 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 2640 KB Output is correct
2 Correct 752 ms 2672 KB Output is correct
3 Correct 714 ms 2660 KB Output is correct
4 Correct 697 ms 2668 KB Output is correct
5 Correct 715 ms 2672 KB Output is correct
6 Correct 710 ms 2672 KB Output is correct
7 Correct 704 ms 2672 KB Output is correct
8 Correct 703 ms 2672 KB Output is correct
9 Correct 705 ms 2672 KB Output is correct
10 Correct 705 ms 2628 KB Output is correct
11 Correct 713 ms 2500 KB Output is correct
12 Correct 705 ms 2500 KB Output is correct
13 Correct 709 ms 2676 KB Output is correct
14 Correct 709 ms 2668 KB Output is correct
15 Correct 708 ms 2668 KB Output is correct
16 Correct 699 ms 2668 KB Output is correct
17 Correct 708 ms 2664 KB Output is correct
18 Correct 696 ms 2628 KB Output is correct
19 Correct 698 ms 2668 KB Output is correct