Submission #1308927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308927		ojuz_user	Data Transfer (IOI19_transfer)	C++20	0 / 100	4 ms	1720 KiB

transfer

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

// Tìm vector chọn (k bit) sao cho XOR các (n+j) với bit=1 bằng target
static vector<int> subset_xor_positions(int n, int k, int target) {
    vector<int> a(k);
    for (int j = 0; j < k; j++) a[j] = n + j;

    // Gaussian elimination trên GF(2) cho số nguyên (bitset 32-bit là đủ)
    vector<int> basis(32, 0);
    vector<int> who(32, 0); // mask trên k phần tử tạo ra basis[b]

    for (int j = 0; j < k; j++) {
        int v = a[j];
        int mask = (1 << j);
        for (int b = 31; b >= 0; b--) {
            if (((v >> b) & 1) == 0) continue;
            if (!basis[b]) {
                basis[b] = v;
                who[b] = mask;
                break;
            }
            v ^= basis[b];
            mask ^= who[b];
        }
    }

    int v = target;
    int mask = 0;
    for (int b = 31; b >= 0; b--) {
        if (((v >> b) & 1) == 0) continue;
        // Với (63,7) và (255,9) thì luôn biểu diễn được
        v ^= basis[b];
        mask ^= who[b];
    }

    vector<int> sel(k, 0);
    for (int j = 0; j < k; j++) sel[j] = (mask >> j) & 1;
    return sel;
}

vector<int> get_attachment(vector<int> source) {
    int n = (int)source.size();
    int k = (n == 63 ? 7 : 9);

    int X = 0;
    for (int i = 0; i < n; i++) if (source[i]) X ^= i;

    // cần XOR(indices của attachment-bit-1) = X để XOR toàn bộ = 0
    return subset_xor_positions(n, k, X);
}

vector<int> retrieve(vector<int> data) {
    int N = (int)data.size();
    int k = (N == 70 ? 7 : 9);
    int n = N - k;

    int p = 0;
    for (int i = 0; i < N; i++) if (data[i]) p ^= i;

    if (p != 0) {
        if (p < n) data[p] ^= 1; // lỗi nằm trong source
        // p >= n: lỗi nằm trong attachment => source ok, khỏi sửa
    }

    data.resize(n);
    return data;
}

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