Submission #599892

#	Time	Username	Problem	Language	Result	Execution time	Memory
599892		jophyyjh	Data Transfer (IOI19_transfer)	C++14	100 / 100	273 ms	2500 KiB

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 / 60
• Subtask 2: 40 / 40