Submission #1136453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136453		noodles0428	Data Transfer (IOI19_transfer)	C++20	100 / 100	130 ms	1728 KiB

transfer

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

#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"

const int N = 1e6 + 9;

int n, a[N];

int rangexor (const vector <int> &v, int be, int en){
    int res = 0; for (int i = be; i < en; i++) res ^= v[i]; return res;
}

int bitxor (const vector <int> &v, int n, int idx){
    int res = 0; for (int i = 0; i < n; i++) if ((i + 1) >> idx & 1) res ^= v[i]; return res;
}

int lg (int val){
    int x = 0; for (int i = val; i > 0; i >>= 1) x++; return x;
}

vector <int> get_attachment (vector <int> source){
    int n = source.size ();
    int _lg = lg (n);
    vector <int> ret;
    for (int i = 0; i < _lg; i++) ret.push_back (bitxor (source, n, i));
    int x = rangexor (ret, 0, _lg);
    ret.push_back (x);
    return ret;
}

vector <int> retrieve (vector <int> data){
    int sz = data.size ();
    int n = sz >> 1;
    while (n + lg (n) + 1 < sz) n++;
    vector <int> res (data.begin (), data.begin () + n);
    vector <int> extra (data.begin () + n, data.end ());
    int len = extra.size () - 1;
    if (extra.back () != rangexor (extra, 0, len)) return res;
    int must = 0;
    for (int i = 0; i < len; i++) if (extra[i] != bitxor (res, n, i)) must |= (1 << i);
    must--;
    if (must >= 0) res[must] ^= 1;
    return res;
}

// love you, noodles0428 <333
// tst25

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