Submission #367628

#	Time	Username	Problem	Language	Result	Execution time	Memory
367628		PurpleCrayon	Data Transfer (IOI19_transfer)	C++17	80 / 100	215 ms	2756 KiB

transfer

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

typedef long long ll;
#define sz(v) int(v.size())

vector<int> get_attachment(vector<int> a) {
    int n = sz(a), B = 31-__builtin_clz(n);

    assert(n&(1<<B)), assert((1<<(B+1))>n);

    vector<int> ans{0};
    for (auto v : a) ans.back() ^= v;
    ans.push_back(ans.back());

    for (int i = 0; i <= B; i++){
        ans.push_back(0);
        for (int j = 0; j < n; j++) if ((j>>i)&1) ans.back() ^= a[j];
    }
    return ans;
}
vector<int> retrieve(vector<int> a) {
    int n=-1;
    if (sz(a) >= 255) n = 255;
    else n = 63;
    int B = 31-__builtin_clz(n);
    assert(n&(1<<B)), assert((1<<(B+1))>n);

    assert(sz(a)==n+1+1+B+1);

    vector<int> ans(a.begin(), a.begin()+n);
    if (a[n] != a[n+1]){
        return ans;
    }
    {
        int c=0;
        for (int i = 0; i < n; i++) c ^= a[i];

        if (c == a[n]) return ans;
    }

    int idx=0;

    for (int i = 0; i <= B; i++){
        int rl=0;
        for (int j = 0; j < n; j++) if ((j>>i)&1) rl ^= a[j];

        if (rl != a[n+2+i]){
            idx ^= 1<<i;
        }
    }
    ans[idx] ^= 1;
    return ans;
}

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