답안 #599892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
599892 2022-07-20T06:26:46 Z jophyyjh Data Transfer (IOI19_transfer) C++14
100 / 100
273 ms 2500 KB
/**
 * 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;
 }
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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