Submission #367629

#	Time	Username	Problem	Language	Result	Execution time	Memory
367629		PurpleCrayon	Data Transfer (IOI19_transfer)	C++17	100 / 100	263 ms	2892 KiB

transfer

#include "transfer.h"
#include <iostream>
using namespace std;
 
//Author: Kian Mirjalali
//K = 1+log(N+1)
 
typedef vector<int> VI;
 
static inline int rangeXorVec(const VI& v, int begin, int end) {
	int s = 0;
	for (int i = begin; i < end; i++)
		s ^= v[i];
	return s;
}
 
static inline int bitMaskXorVec(const VI& v, int N, int bitIndex) {
	int s = 0;
	for (int i = 0; i < N; i++)
		if ((((i + 1) >> bitIndex) & 1) == 1)
			s ^= v[i];
	return s;
}
 
static inline int getL(int N) {
	int L = 0;
	for (int i=N; i>0; i/=2)
		L++;
	return L;
}
 
static inline int callLimit(int N) {
	switch (N) {
	case 63:  return 20000;
	case 255: return 200000;
	}
	cerr << "invalid value of N: " << N << endl;
	exit(1);
}
 
VI get_attachment(VI source) {
	const int N = source.size();
	static int callCount = 0;
	if (++callCount > callLimit(N)) {
		cerr << "too many calls of get_attachment() : " << callCount << endl;
		exit(1);
	}
	int L = getL(N);
	VI attachment;
	for (int l=0; l<L; l++)
		attachment.push_back(bitMaskXorVec(source, N, l));
	attachment.push_back(rangeXorVec(attachment, 0, L));
	return attachment;
}
 
VI retrieve(VI data) {
	int ds = data.size();
	int N = ds/2;
	while (N+getL(N)+1 < ds)
		N++;
	static int callCount = 0;
	if (++callCount > callLimit(N)) {
		cerr << "too many calls of retrieve() : " << callCount << endl;
		exit(1);
	}
	VI result(data.begin(), data.begin()+N);
	VI attachment(data.begin()+N, data.end());
	int L = attachment.size()-1;
	if (attachment.back() != rangeXorVec(attachment, 0, L))
		return result;
	int c = 0;
	for (int l=0; l<L; l++)
		if (attachment[l] != bitMaskXorVec(result, N, l))
			c |= (1<<l);
	c--;
	if (c >= 0)
		result[c] = 1-result[c];
	return result;
}

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