Submission #831521

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
831521	2023-08-20T10:07:39 Z	PanosPask	Data Transfer (IOI19_transfer)	C++14	100 / 100	470 ms	2500 KB

transfer

#include "transfer.h"
#include <math.h>

#define CHECK_BIT(val, pos) ((1 << pos) & val)

using namespace std;

vector<int> get_attachment(vector<int> source) {
	int N = source.size();
	int M = ceil(log2(N));

	vector<int> extra(M, 0);
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (CHECK_BIT(i, j))
				extra[j] ^= source[i];
		}
	}

	for (int j = 0; j < M; j++) {
		extra[j] ^= source[0];
	}

	int xorextra = 0;
	for (int i = 0; i < M; i++)
		xorextra ^= extra[i];
	extra.push_back(xorextra);


	return extra;
}


vector<int> retrieve(vector<int> data) {
	vector<int> source;
	vector<int> extras;

	int xorextra = data.back();
	data.pop_back();

	int N = 1;
	while (N + ceil(log2(N)) < data.size()) {
		N++;
	}
	int M = 0;

	M = ceil(log2(N));

	source = vector<int>(data.begin(), data.begin() + N);
	extras = vector<int>(data.begin() + N, data.end());

	int xorsum = 0;
	for (int i = 0; i < M; i++)
		xorsum ^= extras[i];
	if (xorsum != xorextra) {
		return source;
	}

	vector<int> cur_sum(M, 0);
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (CHECK_BIT(i, j))
				cur_sum[j] ^= source[i];
		}
	}
	for (int j = 0; j < M; j++)
		cur_sum[j] ^= source[0];

	int pos = 0;
	for (int j = 0; j < M; j++) {
		if (extras[j] != cur_sum[j])
			pos += 1 << j;
	}

	if (pos) {
		if (pos == (1 << M) - 1)
			source[0] ^= 1;
		else
			source[pos] ^= 1;
	}

	return source;
}

Subtask #1

60.0 / 60.0

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

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	431 ms	2448 KB	Output is correct
2	Correct	462 ms	2496 KB	Output is correct
3	Correct	438 ms	2488 KB	Output is correct
4	Correct	442 ms	2496 KB	Output is correct
5	Correct	432 ms	2500 KB	Output is correct
6	Correct	459 ms	2488 KB	Output is correct
7	Correct	463 ms	2488 KB	Output is correct
8	Correct	431 ms	2488 KB	Output is correct
9	Correct	453 ms	2488 KB	Output is correct
10	Correct	470 ms	2496 KB	Output is correct
11	Correct	437 ms	2488 KB	Output is correct
12	Correct	431 ms	2496 KB	Output is correct
13	Correct	437 ms	2488 KB	Output is correct
14	Correct	449 ms	2492 KB	Output is correct
15	Correct	433 ms	2496 KB	Output is correct
16	Correct	439 ms	2488 KB	Output is correct
17	Correct	435 ms	2492 KB	Output is correct
18	Correct	453 ms	2456 KB	Output is correct
19	Correct	431 ms	2496 KB	Output is correct