답안 #258629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258629	2020-08-06T09:31:16 Z	ipaljak	Data Transfer (IOI19_transfer)	C++14	100 / 100	752 ms	2676 KB

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.0 / 60.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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