Submission #719704

#	Time	Username	Problem	Language	Result	Execution time	Memory
719704		thimote75	Data Transfer (IOI19_transfer)	C++14	100 / 100	208 ms	2504 KiB

transfer

#include "transfer.h"

#include <bits/stdc++.h>

using namespace std;

#define idata vector<int>

pair<idata, int> make_xor_array (idata source) {
	idata res;
	int sxor = 0;

	for (int h = 0; (1 << h) <= source.size(); h ++) {
		int s   = 1 << h;
		int uxor = 0;
		for (int u = 0; u < source.size(); u ++)
			if ((u & s) == 0)
				uxor ^= source[u];
			
		res.push_back(uxor);
		sxor ^= uxor;
	}

	return { res, sxor };
}
idata get_attachment(idata source) {
	auto v = make_xor_array(source);
	idata res = v.first;
	res.push_back(v.second);

	return res;
}

idata retrieve(idata data) {
	idata source;
	idata xor_array;
	idata expected_xor_array;

	int sxor = data[data.size() - 1];
	int size = (1 << (int) floor(log2(data.size()))) - 1;

	source.resize(size);
	for (int i = 0; i < size; i ++)
		source[i] = data[i];
	int sexor = 0;
	for (int j = size; j + 1 < data.size(); j ++) {
		xor_array.push_back(data[j]);
		sexor ^= data[j];
	}

	if (sexor != sxor) return source;

	expected_xor_array = make_xor_array(source).first;

	int pos = 0;
	for (int h = 0; h < xor_array.size(); h ++)
		if (xor_array[h] == expected_xor_array[h])
			pos |= 1 << h;

	source[pos] = 1 - source[pos];
	return source;
}

Compilation message (stderr)

transfer.cpp: In function 'std::pair<std::vector<int>, int> make_xor_array(std::vector<int>)':
transfer.cpp:13:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int h = 0; (1 << h) <= source.size(); h ++) {
      |                  ~~~~~~~~~^~~~~~~~~~~~~~~~
transfer.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (int u = 0; u < source.size(); u ++)
      |                   ~~^~~~~~~~~~~~~~~
transfer.cpp: In function 'std::vector<int> retrieve(std::vector<int>)':
transfer.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int j = size; j + 1 < data.size(); j ++) {
      |                     ~~~~~~^~~~~~~~~~~~~
transfer.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int h = 0; h < xor_array.size(); h ++)
      |                  ~~^~~~~~~~~~~~~~~~~~

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