Submission #1176571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176571		Zero_OP	Data Transfer (IOI19_transfer)	C++20	100 / 100	125 ms	1728 KiB

transfer

#include "transfer.h"
#include <bits/stdc++.h>

using namespace std;

std::vector<int> get_attachment(std::vector<int> source) {
	int xor_zeroes = 0;
	int N = (int)source.size();
	for(int i = 0; i < N; ++i) if(source[i] == 0) xor_zeroes ^= i+1; //0-based can be misinfomation

	vector<int> attachment;
	int parity = 0;
	for(int i = 0; (1 << i) <= N; ++i) {
		attachment.push_back((xor_zeroes >> i & 1));
		if(xor_zeroes >> i & 1) parity ^= 1;
	}

	attachment.push_back(parity);
	return attachment;
}

std::vector<int> retrieve(std::vector<int> data) {
	int L = (int)data.size();
	int N = -1, bits = -1;
	// for(int i = 0; i < L; ++i) cout << data[i]; cout << '\n';
	for(int i = 1; i < L; ++i){
		int b = 0;
		while((1 << b) <= i) ++b;

		if(i + b + 1 == L){
			N = i;
			bits = b;
			break;
		}
	}

	// cout << N << ' ' << bits << '\n';

	assert(N != -1);

	vector<int> attachment;
	for(int i = 0; i < bits; ++i) attachment.push_back(data[N + i]);

	int A = 0, B = 0, parity1 = data.back(), parity2 = 0;
	for(int i = 0; i < N; ++i) if(data[i] == 0) A ^= i+1;
	for(int i = 0; i < bits; ++i) if(attachment[i]) B ^= (1 << i), parity2 ^= 1;
	
	// cout << parity1 << ' ' << parity2 << '\n';

	if(parity1 != parity2){
		return vector<int>(data.begin(), data.begin() + N);
	}

	int incorrect = A ^ B;
	// cout << A << ' ' << B << '\n';
	if(!incorrect) return vector<int>(data.begin(), data.begin() + N);
	// cout << incorrect << '\n';
	data[incorrect-1] ^= 1;
	return vector<int>(data.begin(), data.begin() + N);
}

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