/**
* 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 |
