Submission #1320633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320633		hoangtung121212	Data Transfer (IOI19_transfer)	C++20	100 / 100	60 ms	1712 KiB

transfer

#include <bits/stdc++.h>
using namespace std;

static int smallest_k(int n){
    int k = 0;
    while (n + k > (1 << k) - 1) k++;
    return k;
}

static bool is_pow2(int x){
    return x && ((x & (x - 1)) == 0);
}

vector<int> get_attachment(vector<int> source) {
    int n = (int)source.size();
    int k = smallest_k(n);

    // assign a unique nonzero k-bit column to each data bit, excluding powers of two
    vector<int> col(n);
    int v = 1;
    for(int i = 0; i < n; i++){
        while (v < (1 << k) && is_pow2(v)) v++;
        col[i] = v;
        v++;
    }

    vector<int> parity(k, 0);

    // parity[j] = XOR of source[i] for which col[i] has bit j
    for(int i = 0; i < n; i++){
        if(source[i] == 0) continue;
        for(int j = 0; j < k; j++){
            if(col[i] & (1 << j)) parity[j] ^= 1;
        }
    }

    return parity; // appended to source
}

vector<int> retrieve(vector<int> data) {
    int N = (int)data.size();

    // find n and k? We don't know n directly, but k is small; however in this task
    // the judge calls retrieve with "source + attachment", so we can deduce k by trying.
    // easiest: k is the smallest such that N <= 2^k - 1 (since N = n + k and n+k <= 2^k-1)
    int k = 0;
    while (N > (1 << k) - 1) k++;

    int n = N - k;

    // rebuild same columns used in get_attachment
    vector<int> col(n);
    int v = 1;
    for(int i = 0; i < n; i++){
        while (v < (1 << k) && is_pow2(v)) v++;
        col[i] = v;
        v++;
    }

    // compute syndrome s (k-bit number)
    int s = 0;

    // data part
    for(int i = 0; i < n; i++){
        if(data[i]) s ^= col[i];
    }

    // parity/attachment part: parity bit j has column (1<<j)
    for(int j = 0; j < k; j++){
        if(data[n + j]) s ^= (1 << j);
    }

    // correct if needed
    if(s != 0){
        if(is_pow2(s)){
            // error in parity bit: flip it if you want (not necessary for returning source)
            int j = __builtin_ctz(s);
            if(j >= 0 && j < k) data[n + j] ^= 1;
        } else {
            // error in a data bit: find which i has col[i] == s
            for(int i = 0; i < n; i++){
                if(col[i] == s){
                    data[i] ^= 1;
                    break;
                }
            }
        }
    }

    // return corrected source bits (first n bits)
    vector<int> source(n);
    for(int i = 0; i < n; i++) source[i] = data[i];
    return source;
}

Compilation message (stderr)

grader.cpp: In instantiation of 'void shuffle(std::vector<T>&) [with T = Scenario]':
grader.cpp:200:10:   required from here
grader.cpp:28:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Scenario*, vector<Scenario> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   28 |         random_shuffle(v.begin(), v.end());
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from grader.cpp:8:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

• Subtask 1: 60 / 60
• Subtask 2: 40 / 40