Submission #599892

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
599892	2022-07-20T06:26:46 Z	jophyyjh	Data Transfer (IOI19_transfer)	C++14	100 / 100	273 ms	2500 KB

transfer

/**
 * Well, i've seen this trick in an Olympic Maths combinactorics book (Olympic
 * Combinactorics Book1, i guess), though i guess this communication problem would
 * still be pretty interesting for those who haven't. Suppose that set A contains
 * the original N bits, set B contains ceil(log_2(n)) bits and set C contains a
 * single bit, which is the xor of all bits in B.
 * 
 * We solve this problem by using the fact that each int has a UNIQUE binary repr.
 * The i-th bit in B equals the xor of all bits in A (whose index(<=N, >0)'s i-th
 * bit is a 1). The sole bit in set C can just be the xor of all bits in B. 1-indexed
 * is used to ensure that if a bit in A is corruputed, at least 1 bit in B is
 * changed.
 * 
 * Q: log_2(n)
 * Implementation 1
*/

#include <bits/stdc++.h>
#include "transfer.h"

typedef std::vector<int>	vec;

const int N1 = 63, B1 = 6, SIZE1 = 70;
const int N2 = 255, B2 = 8, SIZE2 = 264;


vec get_attachment(vec source) {
	int n = source.size(), B = (n == N2 ? B2 : B1);
	vec encoded(B + 1, 0);
	for (int k = 0; k < n; k++) {
		for (int k_copy = k + 1, bit = 0; k_copy > 0; k_copy >>= 1, bit++) {
			if (k_copy & 1)
				encoded[bit] ^= source[k];
		}
	}
	for (int k = 0; k < B; k++)
		encoded[B] ^= encoded[k];
	return encoded;
}

vec retrieve(vec data) {
	int n = (data.size() == SIZE2 ? N2 : N1), B = (n == N2 ? B2 : B1);
	std::vector<bool> correct(B);
	vec compute(B, 0);
	for (int k = 0; k < n; k++) {
		for (int k_copy = k + 1, bit = 0; k_copy > 0; k_copy >>= 1, bit++) {
			if (k_copy & 1)
				compute[bit] ^= data[k];
		}
	}
	bool set_B_xor = 0;
	for (int i = 0; i < B; i++)
		correct[i] = (compute[i] == data[i + n]), set_B_xor ^= data[i + n];
	
	bool AB_correct = true;
	for (int i = 0; i < B && AB_correct; i++)
		AB_correct &= correct[i];
	if (!AB_correct && set_B_xor == data[n + B]) {
		int corrupt_bit = 0;
		for (int k = 0; k < B; k++) {
			if (!correct[k])
				corrupt_bit |= (1 << k);
		}
		data[corrupt_bit - 1] ^= 1;
	}
	data.resize(n);		// truncate the array
	return data;
 }

Subtask #1

60.0 / 60.0

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

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	235 ms	2444 KB	Output is correct
2	Correct	238 ms	2488 KB	Output is correct
3	Correct	226 ms	2488 KB	Output is correct
4	Correct	228 ms	2488 KB	Output is correct
5	Correct	227 ms	2484 KB	Output is correct
6	Correct	230 ms	2500 KB	Output is correct
7	Correct	240 ms	2488 KB	Output is correct
8	Correct	243 ms	2488 KB	Output is correct
9	Correct	243 ms	2488 KB	Output is correct
10	Correct	236 ms	2496 KB	Output is correct
11	Correct	222 ms	2496 KB	Output is correct
12	Correct	254 ms	2452 KB	Output is correct
13	Correct	225 ms	2488 KB	Output is correct
14	Correct	226 ms	2496 KB	Output is correct
15	Correct	246 ms	2360 KB	Output is correct
16	Correct	273 ms	2488 KB	Output is correct
17	Correct	233 ms	2492 KB	Output is correct
18	Correct	246 ms	2496 KB	Output is correct
19	Correct	246 ms	2496 KB	Output is correct