Submission #145190

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
145190	2019-08-19T08:38:37 Z	ecnerwala	Data Transfer (IOI19_transfer)	C++14	100 / 100	351 ms	2980 KB

transfer

#include "transfer.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> get_attachment(std::vector<int> source) {
	int N = int(source.size());
	int v = 0;
	for (int i = 0; i < N; i++) {
		v ^= source[i];
	}
	source.push_back(v);
	vector<int> result({v});
	for (int i = 0; (1 << i) < N+1; i++) {
		result.push_back(0);
		for (int j = 0; j < N+1; j++) {
			if (j & (1 << i)) {
				result.back() ^= source[j];
			}
		}
	}
	return result;
}

std::vector<int> retrieve(std::vector<int> data) {
	int N;
	if (data.size() == 63 + 7) {
		N = 63;
	} else if (data.size() == 255 + 9) {
		N = 255;
	} else assert(false);
	vector<int> source(data.begin(), data.begin()+N);
	vector<int> badAttachment = get_attachment(source);
	vector<int> trueAttachment(data.begin()+N, data.end());
	if (badAttachment[0] == trueAttachment[0]) {
		return source;
	} else {
		int ind = 0;
		for (int i = 0; (1 << i) < N+1; i++) {
			if ((badAttachment[i+1]^1) != trueAttachment[i+1]) {
				ind |= (1 << i);
			}
		}
		if (ind < N) {
			source[ind] ^= 1;
		}
		return source;
	}
}

Subtask #1

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	892 KB	Output is correct
2	Correct	10 ms	1132 KB	Output is correct
3	Correct	11 ms	1004 KB	Output is correct
4	Correct	10 ms	1104 KB	Output is correct
5	Correct	11 ms	920 KB	Output is correct
6	Correct	10 ms	1020 KB	Output is correct
7	Correct	10 ms	1024 KB	Output is correct
8	Correct	10 ms	1100 KB	Output is correct
9	Correct	11 ms	1156 KB	Output is correct
10	Correct	11 ms	1028 KB	Output is correct
11	Correct	10 ms	892 KB	Output is correct
12	Correct	11 ms	1028 KB	Output is correct
13	Correct	10 ms	892 KB	Output is correct
14	Correct	10 ms	980 KB	Output is correct
15	Correct	11 ms	1108 KB	Output is correct
16	Correct	10 ms	976 KB	Output is correct
17	Correct	10 ms	1028 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	340 ms	2608 KB	Output is correct
2	Correct	338 ms	2980 KB	Output is correct
3	Correct	338 ms	2608 KB	Output is correct
4	Correct	333 ms	2480 KB	Output is correct
5	Correct	335 ms	2616 KB	Output is correct
6	Correct	335 ms	2608 KB	Output is correct
7	Correct	339 ms	2480 KB	Output is correct
8	Correct	334 ms	2480 KB	Output is correct
9	Correct	337 ms	2612 KB	Output is correct
10	Correct	333 ms	2608 KB	Output is correct
11	Correct	336 ms	2620 KB	Output is correct
12	Correct	335 ms	2628 KB	Output is correct
13	Correct	333 ms	2628 KB	Output is correct
14	Correct	336 ms	2620 KB	Output is correct
15	Correct	350 ms	2620 KB	Output is correct
16	Correct	334 ms	2652 KB	Output is correct
17	Correct	333 ms	2748 KB	Output is correct
18	Correct	347 ms	2480 KB	Output is correct
19	Correct	351 ms	2476 KB	Output is correct