Submission #1132247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132247		totoro	Data Transfer (IOI19_transfer)	C++20	0 / 100	5 ms	1724 KiB

transfer

#include "transfer.h"
#include <vector>
#include <iostream>
#include <cassert>

std::vector<int> get_attachment(std::vector<int> source) {
	std::vector<int> res;
	for (int i = 0; (1 << i) < source.size(); ++i) {
		int xorsum = 0;
		for (int j = 0; j < source.size(); ++j) {
			if (((j >> i) & 1) == 0) continue;
			xorsum ^= source[j];
		}
		res.push_back(xorsum);
	}
	int parity = 0;
	for (int i : res) parity ^= i;
	res.push_back(parity);
	return res;
}

int log2(int n) {
	int log = 0;
	while (n) ++log, n >>= 1;
	return log;
}

std::vector<int> retrieve(std::vector<int> data) {
	int parity = data.back(); data.pop_back();
	int extra = log2(data.size());
	while (log2(data.size() - extra) < extra) --extra;
	// std::cout << extra << std::endl;
	// for (auto el : data) std::cout << el;
	// std::cout << std::endl;
	int bad = 0;
	for (int i = 0; i < extra; ++i) {
		int xorsum = data[data.size() - extra + i];
		// std::cout << "INFO: " <<  xorsum << std::endl;
		for (int j = 0; j < data.size() - extra; ++j) {
			if (((j >> i) & 1) == 0) continue;
			xorsum ^= data[j];
			// std::cout << "INFOOO: " <<  xorsum << std::endl;
		}
		assert(xorsum <= 1);
		bad ^= xorsum << i;
	}
	for (int i = data.size() - extra; i < data.size(); ++i) {
		parity ^= data[i];
	}
	if (parity) bad = -1;
	for (int i = 0; i < data.size(); ++i) {
		data[i] ^= i==bad;
	}
	// std::cout << bad << std::endl;
	std::vector<int> res;
	for (int i = 0; i < data.size() - extra; ++i) {
		res.push_back(data[i]);
	}
	return res;
}

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