Submission #748036

#	Time	Username	Problem	Language	Result	Execution time	Memory
748036		FulopMate	Data Transfer (IOI19_transfer)	C++17	80 / 100	1694 ms	2512 KiB

transfer

#include "transfer.h"

#include <bits/stdc++.h>

using namespace std;

vector<int> get_attachment(vector<int> source) {
	vector<int> res;
	int K = log2(source.size()+1);
	int safe = 0;
	for (int i = 0; i <= K; i++) {
		int x = 0;
		int block = 1 << i;
		for (int j = 0; j < source.size(); j++) {
			if ((j / block) % 2 == 0) {
				x ^= source[j];
			}
		}
		res.push_back(x);
		safe ^= x;
	}
	res.push_back(safe);
	return res;
}

vector<int> retrieve(vector<int> data) {
	int n;
	if (data.size() < 100) {
		n = 63;
	} else {
		n = 255;
	}
	int K = log2(n+1);
	int safe = data.back();
	vector<int> source = vector<int>(data.begin(), data.begin()+n);
	vector<int> cnt(n);
	vector<int> v = vector<int>(data.begin()+n, data.end()-1);
	int p = 0;
	for (int i : v) p ^= i;
	if (p != safe) return source;
	for (int i = 0; i <= K; i++) {
		int x = 0;
		int block = 1 << i;
		for (int j = 0; j < n; j++) {
			if ((j / block) % 2 == 0) {
				x ^= source[j];
			}
		}
		for (int j = 0; j < n; j++) {
			if ((j / block) % 2 == (x == v[i])) {
				cnt[j]++;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (cnt[i] == K+1) {
			source[i] ^= 1;
			return source;
		}
	}
	return source;
}

Compilation message (stderr)

transfer.cpp: In function 'std::vector<int> get_attachment(std::vector<int>)':
transfer.cpp:14:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for (int j = 0; j < source.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~

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