Submission #770933

#	Time	Username	Problem	Language	Result	Execution time	Memory
770933		rxlfd314	Data Transfer (IOI19_transfer)	C++17	100 / 100	631 ms	2504 KiB

transfer

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

void yeet(int n, vector<int> &v, vector<int> &source) {
	for (int j = 0; (1 << j) <= n; j++) {
		v.push_back(0);
		for (int i = 1; i <= n; i++) {
			if (i & 1 << j) {
				v[j] ^= source[i-1];
			}
		}
	}
}

vector<int> get_attachment(vector<int> source) {
	int N = source.size();
	vector<int> ret;
	yeet(N, ret, source);
	ret.push_back(0);
	for (int i = 0; i < N; i++) {
		ret.back() ^= source[i];
	}
	return ret;
}

vector<int> retrieve(vector<int> data) {
	int N = data.size() < 255 ? 63 : 255;
	int M = data.size();
	vector<int> test;
	yeet(N, test, data);
	if (test == vector<int>(data.begin()+N, data.begin()+M-1)) {
		return vector<int>(data.begin(), data.begin()+N);
	}
	bool p = 0;
	for (int i = 0; i < N; i++) {
		p ^= data[i];
	}
	if (p ^ data[M-1]) {
		for (int i = 1; i <= N; i++) {
			for (int j = 0; (1 << j) <= N; j++) {
				if (i & 1 << j) {
					test[j] ^= 1;
				}
			}
			if (test == vector<int>(data.begin()+N, data.begin()+M-1)) {
				data[i-1] ^= 1;
				return vector<int>(data.begin(), data.begin()+N);
			}
			for (int j = 0; (1 << j) <= N; j++) {
				if (i & 1 << j) {
					test[j] ^= 1;
				}
			}
		}
	}
	return vector<int>(data.begin(), data.begin()+N);
}

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