Submission #1165500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165500		gustavo_d	Data Transfer (IOI19_transfer)	C++20	100 / 100	87 ms	1728 KiB

transfer

#include "transfer.h"
#include <bits/stdc++.h>
using namespace std;

int calcXor(vector<int> &a, int l, int r) {
	int x = 0;
	for (int i=l; i<=r; i++) x ^= a[i];
	return x;
}

vector<int> calculateXors(vector<int> &source) {
	int n = 1;
	while (n < (int)source.size()) n <<= 1;

	vector<int> tmp(n, 0);
	for (int i=0; i<(int)source.size(); i++) tmp[i] = source[i];

	vector<int> bits;
	for (int b=0; (1 << b) < n; b++) {
		int Xor = 0;
		for (int i=0; i<n; i+=2*(1 << b)) {
			Xor ^= calcXor(tmp, i, i+(1 << b)-1);
		}
		bits.push_back(Xor);
	}
	reverse(bits.begin(), bits.end());

	bits.push_back(calcXor(source, 0, (int)source.size() - 1));

	return bits;
}

vector<int> get_attachment(vector<int> source) {
	return calculateXors(source);
}

vector<int> retrieve(vector<int> data) {
	// for (int d : data) cout << d << ' ';
	// cout << endl;

	int n;
	if ((int)data.size() <= 100) n = 63;
	else n = 255;

	vector<int> src(n);
	for (int i=0; i<n; i++) src[i] = data[i];
	vector<int> bits;
	for (int i=n; i<(int)data.size()-1; i++)
		bits.push_back(data[i]);
	int checkerBit = data.back();

	vector<int> expectedBits = calculateXors(src);
	int expectedChecker = expectedBits.back();

	if (expectedChecker == checkerBit) {
		return src;
	} // corrompeu bits

	int l = 0, r = n-1; int pt = 0, ans = -1;
	while (l <= r) {
		int m = (l + r) / 2;

		if (bits[pt] != expectedBits[pt]) {
			r = m-1;
			ans = m;
		} else l = m+1;
		pt++;
	}

	if (ans != -1) src[ans] = !src[ans];

	return src;
}

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