Submission #367629

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
367629	2021-02-17T19:15:51 Z	PurpleCrayon	Data Transfer (IOI19_transfer)	C++17	100 / 100	263 ms	2892 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	5 ms	876 KB	Output is correct
2	Correct	5 ms	876 KB	Output is correct
3	Correct	6 ms	1092 KB	Output is correct
4	Correct	5 ms	1004 KB	Output is correct
5	Correct	5 ms	1132 KB	Output is correct
6	Correct	5 ms	876 KB	Output is correct
7	Correct	5 ms	1092 KB	Output is correct
8	Correct	6 ms	876 KB	Output is correct
9	Correct	5 ms	1004 KB	Output is correct
10	Correct	5 ms	916 KB	Output is correct
11	Correct	5 ms	916 KB	Output is correct
12	Correct	6 ms	876 KB	Output is correct
13	Correct	5 ms	1100 KB	Output is correct
14	Correct	7 ms	876 KB	Output is correct
15	Correct	5 ms	1004 KB	Output is correct
16	Correct	5 ms	876 KB	Output is correct
17	Correct	6 ms	1092 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	227 ms	2632 KB	Output is correct
2	Correct	223 ms	2464 KB	Output is correct
3	Correct	225 ms	2464 KB	Output is correct
4	Correct	225 ms	2648 KB	Output is correct
5	Correct	222 ms	2644 KB	Output is correct
6	Correct	222 ms	2612 KB	Output is correct
7	Correct	224 ms	2464 KB	Output is correct
8	Correct	241 ms	2612 KB	Output is correct
9	Correct	225 ms	2464 KB	Output is correct
10	Correct	263 ms	2764 KB	Output is correct
11	Correct	256 ms	2624 KB	Output is correct
12	Correct	223 ms	2892 KB	Output is correct
13	Correct	225 ms	2464 KB	Output is correct
14	Correct	230 ms	2612 KB	Output is correct
15	Correct	235 ms	2464 KB	Output is correct
16	Correct	223 ms	2464 KB	Output is correct
17	Correct	222 ms	2636 KB	Output is correct
18	Correct	225 ms	2464 KB	Output is correct
19	Correct	237 ms	2612 KB	Output is correct