Submission #143438

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
143438	2019-08-14T05:20:17 Z	model_code	Data Transfer (IOI19_transfer)	C++17	100 / 100	221 ms	2632 KB

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.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	888 KB	Output is correct
2	Correct	8 ms	1132 KB	Output is correct
3	Correct	8 ms	1016 KB	Output is correct
4	Correct	8 ms	1028 KB	Output is correct
5	Correct	8 ms	976 KB	Output is correct
6	Correct	8 ms	896 KB	Output is correct
7	Correct	8 ms	972 KB	Output is correct
8	Correct	8 ms	1024 KB	Output is correct
9	Correct	8 ms	1016 KB	Output is correct
10	Correct	8 ms	1132 KB	Output is correct
11	Correct	8 ms	1024 KB	Output is correct
12	Correct	8 ms	1016 KB	Output is correct
13	Correct	8 ms	892 KB	Output is correct
14	Correct	8 ms	896 KB	Output is correct
15	Correct	8 ms	888 KB	Output is correct
16	Correct	8 ms	888 KB	Output is correct
17	Correct	8 ms	888 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	220 ms	2604 KB	Output is correct
2	Correct	220 ms	2620 KB	Output is correct
3	Correct	220 ms	2608 KB	Output is correct
4	Correct	221 ms	2612 KB	Output is correct
5	Correct	220 ms	2624 KB	Output is correct
6	Correct	221 ms	2604 KB	Output is correct
7	Correct	220 ms	2484 KB	Output is correct
8	Correct	220 ms	2472 KB	Output is correct
9	Correct	220 ms	2632 KB	Output is correct
10	Correct	220 ms	2476 KB	Output is correct
11	Correct	220 ms	2604 KB	Output is correct
12	Correct	219 ms	2604 KB	Output is correct
13	Correct	219 ms	2604 KB	Output is correct
14	Correct	220 ms	2608 KB	Output is correct
15	Correct	220 ms	2628 KB	Output is correct
16	Correct	220 ms	2476 KB	Output is correct
17	Correct	220 ms	2620 KB	Output is correct
18	Correct	220 ms	2604 KB	Output is correct
19	Correct	220 ms	2476 KB	Output is correct