Submission #143974

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
143974	2019-08-15T14:04:36 Z	nvmdava	Data Transfer (IOI19_transfer)	C++17	100 / 100	226 ms	2616 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	976 KB	Output is correct
3	Correct	8 ms	896 KB	Output is correct
4	Correct	8 ms	1016 KB	Output is correct
5	Correct	8 ms	996 KB	Output is correct
6	Correct	8 ms	888 KB	Output is correct
7	Correct	8 ms	888 KB	Output is correct
8	Correct	8 ms	888 KB	Output is correct
9	Correct	8 ms	1028 KB	Output is correct
10	Correct	8 ms	1024 KB	Output is correct
11	Correct	8 ms	1016 KB	Output is correct
12	Correct	8 ms	976 KB	Output is correct
13	Correct	8 ms	896 KB	Output is correct
14	Correct	8 ms	924 KB	Output is correct
15	Correct	8 ms	972 KB	Output is correct
16	Correct	8 ms	972 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	221 ms	2476 KB	Output is correct
2	Correct	222 ms	2604 KB	Output is correct
3	Correct	222 ms	2612 KB	Output is correct
4	Correct	221 ms	2480 KB	Output is correct
5	Correct	221 ms	2612 KB	Output is correct
6	Correct	225 ms	2476 KB	Output is correct
7	Correct	225 ms	2480 KB	Output is correct
8	Correct	220 ms	2616 KB	Output is correct
9	Correct	221 ms	2604 KB	Output is correct
10	Correct	220 ms	2472 KB	Output is correct
11	Correct	226 ms	2604 KB	Output is correct
12	Correct	220 ms	2600 KB	Output is correct
13	Correct	221 ms	2604 KB	Output is correct
14	Correct	219 ms	2604 KB	Output is correct
15	Correct	223 ms	2600 KB	Output is correct
16	Correct	221 ms	2476 KB	Output is correct
17	Correct	220 ms	2472 KB	Output is correct
18	Correct	222 ms	2604 KB	Output is correct
19	Correct	224 ms	2604 KB	Output is correct