Submission #679261

#	Time	Username	Problem	Language	Result	Execution time	Memory
679261		That_Salamander	Data Transfer (IOI19_transfer)	C++14	100 / 100	246 ms	2500 KiB

transfer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<int> get_attachment(vector<int> source) {
    vector<int> hamming;

    int m = 1;
    int x2 = 0;
    while (m <= source.size()) {
        int x = 0;
        for (int i = 0; i < source.size(); i++) {
            if (!(i & m)) {
                x ^= source[i];
            }
        }
        hamming.push_back(x);
        x2 ^= x;

        m <<= 1;
    }

    hamming.push_back(x2);
    return hamming;
}

vector<int> retrieve(vector<int> data) {
    int n = data.size() >= 255 ? 255 : 63;
    int h = data.size() - n - 1;

    vector<int> source(data.begin(), data.begin()+ n);

    vector<int> hamming(h);

    int x = 0;
    for (int i = 0; i < h; i++) {
        x ^= hamming[i] = data[n + i];
    }

    if (x != data[n + h]) return source;

    vector<int> correct(h);
    bool valid = true;
    for (int i = 0; i < h; i++) {
        int x = 0;
        for (int j = 0; j < n; j++) {
            if (!((j >> i) & 1)) {
                x ^= source[j];
            }
        }

        correct[i] = x == hamming[i];
        if (!correct[i]) valid = false;
    }

    if (valid) return source;

    int idx = 0;
    for (int i = 0; i < h; i++) {
        if (correct[i]) {
            idx += 1 << i;
        }
    }

    source[idx] ^= 1;

    return source;
}

#ifdef LOCAL_TEST
#include <random>

vector<int> manipulate(vector<int>& data) {
    vector<int> res = data;
    
    if (rand() % 2) {
        res[rand() % res.size()] ^= 1;
    }

    return res;
}

void doTest() {
    int n = rand() % 2 ? 63 : 255;

    vector<int> data(n);
    for (int& x: data) {
        x = rand() % 2;
    }

    vector<int> attached = data;
    for (int x: get_attachment(data)) {
        attached.push_back(x);
    }

    if (retrieve(manipulate(attached)) != data) {
        cout << "Error!" << endl;
    }
}

int main() {
    for (int i = 0; i < 200000; i++) {
        doTest();
    }

    cout << "Finished!" << endl;
}
#endif

Compilation message (stderr)

transfer.cpp: In function 'std::vector<int> get_attachment(std::vector<int>)':
transfer.cpp:11:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     while (m <= source.size()) {
      |            ~~^~~~~~~~~~~~~~~~
transfer.cpp:13:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         for (int i = 0; i < source.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~

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