Submission #829961

#	Time	Username	Problem	Language	Result	Execution time	Memory
829961		somethingnew	Data Transfer (IOI19_transfer)	C++17	100 / 100	317 ms	2496 KiB

transfer

#include <iostream>

#include "algorithm"
#include "array"
#include "bitset"
#include "climits"
#include "cmath"
#include "deque"
#include "iomanip"
#include "map"
#include "numeric"
#include "set"
#include "transfer.h"
#include "vector"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
vector<int> rearange(vector<int> a, int k) {
    int n = sz(a) - k;
    vector<int> b(sz(a));
    for (int i = 0; i < k; i++) {
        b[1 << i] = 1;
    }
    int ind = 0;
    for (int i = 0; i < sz(a) - k; i++) {
        while (b[ind] == 1) {
            ind++;
        }
        if (ind < sz(b)) {
            b[ind] = a[i];
            ind++;
        } else {
            cout << "FAC" << ind << endl;
        }
    }
    for (int i = 0; i < k; i++) {
        b[1 << i] = a[n + i];
    }
    return b;
}
vector<int> rearange2(vector<int> a, int k) {
    int n = sz(a) - k;
    vector<int> b(sz(a)), c = b;
    for (int i = 0; i < k; i++) {
        b[1 << i] = 1;
    }
    int ind = 0;
    for (int i = 0; i < sz(a) - k; i++) {
        while (ind < sz(b) and b[ind] == 1) {
            ind++;
        }
        if (ind < sz(c))
            c[i] = a[ind];
        else {
            cout << "BLYA" << ind << endl;
        }
        ind++;
    }
    for (int i = 0; i < k; i++) {
        c[n + i] = a[1 << i];
    }
    return c;
}
void addzer(vector<int> &a) {
    vector<int> b = {0};
    for (auto i : a) {
        b.push_back(i);
    }
    swap(a, b);
}
vector<int> get_attachment(vector<int> source) {
    addzer(source);
    int n = sz(source);
    int k = 7;
    if (n > 90)
        k = 9;
    vector<int> beba(k);
    for (int i = 0; i < k; i++) {
        source.push_back(0);
    }
    // for (auto i : source)
    //     cout << i;
    // cout << '\n';
    source = rearange(source, k);
    // source = rearange2(source, k);
    // for (auto i : source)
    //    cout << i;
    // cout << '\n';
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n + k; j++) {
            if (j & (1 << i))
                beba[i] ^= source[j];
        }
    }
    return beba;
}
vector<int> retrieve(vector<int> data) {
    addzer(data);
    int n = sz(data);
    int k = 7;
    if (n > 90)
        k = 9;
    n -= k;
    for (int i = n; i < n + k; i++) {
        // data[i] = 2 + i - n;
    }

    // for (auto i : data)
    //     cout << i;
    //  cout << '\n';
    data = rearange(data, k);
    // for (auto i : data)
    //     cout << i;
    //  cout << '\n';
    //   cout << n << ' ' << k << '\n';
    vector<int> beba(k);
    int ind = 0;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n + k; j++) {
            if (j & (1 << i))
                beba[i] ^= data[j];
        }
        if (beba[i] != 0)
            ind += (1 << i);
    }
    // cerr << ind << endl;
    //  exit(0);
    data[ind] ^= 1;

    data = rearange2(data, k);
    vector<int> res;
    for (int i = 1; i < n; i++) {
        res.push_back(data[i]);
        // cout << data[i];
    }
    // cout << endl;
    return res;
}

#ifdef LOCAL

static inline string run_scenario() {
    int c;
    cin >> c;
    if (c < -1)
        return "invalid corruption index";
    string source_str;
    cin >> source_str;
    const int N = source_str.size();
    const int max_attachment_size = 2 * N;
    vector<int> source;
    for (int i = 0; i < N; i++)
        source.push_back(source_str[i] - '0');

    vector<int> attachment = get_attachment(source);
    if (int(attachment.size()) > max_attachment_size)
        return "attachment too large";
    for (int x : attachment)
        if (x != 0 && x != 1)
            return "invalid attachment integer value";

    vector<int> data(source);
    data.insert(data.end(), attachment.begin(), attachment.end());

    if (c >= int(data.size()))
        return "invalid corruption index";

    if (c >= 0)
        data[c] = 1 - data[c];

    vector<int> result_source = retrieve(data);

    if (source != result_source)
        return "wrong source retrieval";

    return string("OK K=") + to_string(attachment.size());
}

int main() {
    freopen("inp.txt", "r", stdin);
    int T;
    cin >> T;
    for (int scenario = 0; scenario < T; scenario++) {
        string result = run_scenario();
        cout << "scenario #" << scenario << ": " << result << endl;
    }
    return 0;
}
#endif

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