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
#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;
}
# 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
# 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