Submission #735873

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
735873	2023-05-04T21:04:12 Z	rnl42	Data Transfer (IOI19_transfer)	C++14	100 / 100	266 ms	2504 KB

transfer

#include "transfer.h"
using namespace std;
#include <iostream>

vector<int> get_attachment(vector<int> source) {
	const int N = source.size();
	//assert(__builtin_popcount(N+1) == 1);
	const int K = __lg(N+1)+1;
	vector<int> attach(K);
	for (int i = 0; i < N; i++) {
		for (int b = 0; b < K-1; b++) {
			if (((i+1) >> b) & 1) {
				attach[b] ^= source[i];
			}
		}
		attach.back() ^= source[i];
	}
	return attach;
}

vector<int> retrieve(vector<int> data) {
	int N = data.size();
	int K = __lg(N)+1;
	N -= K;

	vector<int> source(data.begin(), data.begin() + N);
	vector<int> newattach = get_attachment(source);
	int i = 0;
	for (int b = 0; b < K-1; b++) {
		if (newattach[b] != data[N+b]) {
			i |= (1<<b);
		}
	}
	i--;
	if (newattach.back() != data.back()) {
		if (i != -1) source[i] ^= 1;
	}
	return source;
}

Subtask #1

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	652 KB	Output is correct
2	Correct	5 ms	740 KB	Output is correct
3	Correct	5 ms	644 KB	Output is correct
4	Correct	5 ms	652 KB	Output is correct
5	Correct	5 ms	644 KB	Output is correct
6	Correct	5 ms	644 KB	Output is correct
7	Correct	5 ms	644 KB	Output is correct
8	Correct	5 ms	644 KB	Output is correct
9	Correct	5 ms	644 KB	Output is correct
10	Correct	5 ms	728 KB	Output is correct
11	Correct	5 ms	736 KB	Output is correct
12	Correct	5 ms	644 KB	Output is correct
13	Correct	5 ms	640 KB	Output is correct
14	Correct	5 ms	652 KB	Output is correct
15	Correct	5 ms	736 KB	Output is correct
16	Correct	5 ms	736 KB	Output is correct
17	Correct	5 ms	652 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	246 ms	2492 KB	Output is correct
2	Correct	256 ms	2488 KB	Output is correct
3	Correct	254 ms	2500 KB	Output is correct
4	Correct	250 ms	2488 KB	Output is correct
5	Correct	251 ms	2488 KB	Output is correct
6	Correct	251 ms	2488 KB	Output is correct
7	Correct	257 ms	2500 KB	Output is correct
8	Correct	248 ms	2500 KB	Output is correct
9	Correct	262 ms	2488 KB	Output is correct
10	Correct	253 ms	2444 KB	Output is correct
11	Correct	255 ms	2504 KB	Output is correct
12	Correct	259 ms	2500 KB	Output is correct
13	Correct	255 ms	2500 KB	Output is correct
14	Correct	249 ms	2500 KB	Output is correct
15	Correct	254 ms	2500 KB	Output is correct
16	Correct	251 ms	2504 KB	Output is correct
17	Correct	259 ms	2496 KB	Output is correct
18	Correct	253 ms	2500 KB	Output is correct
19	Correct	266 ms	2488 KB	Output is correct