Submission #1141432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141432		MrAndria	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	267 ms	8260 KiB

xorsum

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

#define FOR(i,a,b) for(int i = a; i < b; i++)

typedef long long ll;
int ans;


void flatten (int a[], int alen, int nbits) {
    int mask = (1 << nbits) - 1;
    FOR(i, 0, alen) {
        a[i] = a[i] & mask;
    }
}

ll num_sums_gt(int a[], int alen, int b[], int blen, int k) {
    ll tot = 0;
    int ia = alen;
    for (int ib = 0; ib < blen; ib++) {
        while (ia > 0 && a[ia-1] + b[ib] > k) {
            ia--;
        }
        tot += (alen-ia);
    }
    return tot;
}

// std::merge already exists, but it's not in-place
void mymerge (int a[], int alen, int lhs_len) {
    int lhs[lhs_len];
    int *rhs = a + lhs_len;
    int lhs_start = 0;
    int rhs_start = 0;
    int rhs_len = alen - lhs_len;
    for (int i = 0; i < lhs_len; i++) {
        lhs[i] = a[i];
    }
    for (int i = 0; i < alen; i++) {
        if (rhs_start == rhs_len || (lhs_start < lhs_len && lhs[lhs_start] < rhs[rhs_start])) {
            a[i] = lhs[lhs_start];
            lhs_start++;
        } else {
            a[i] = rhs[rhs_start];
            rhs_start++;
        }
    }
}

int self_psum_xor (int a[], int alen, int nbits) {
    int total = 0;
    while (nbits > 0) {
        int biggest_small = (1 << (nbits-1)) - 1;
        int* mid_ptr = upper_bound(a, a+alen, biggest_small);
        int num_smalls = mid_ptr - a;
        int num_bigs = alen - num_smalls;
        flatten(a + num_smalls, num_bigs, nbits-1);
        ll ngt = num_sums_gt(a, num_smalls, a+num_smalls, num_bigs, biggest_small);
        total = total ^ (((num_bigs % 4)/2) << nbits);
        total = total ^ (((num_bigs % 2) * (num_smalls % 2)) << (nbits-1));
        total = total ^ ((ngt % 2) << (nbits));

        mymerge(a, alen, num_smalls);
        nbits--;
    }
    return total;
}

void run() {
    int n;
    cin >> n;
    int a[n];
    FOR(i,0,n) {cin >> a[i];}

    for(int i=0;i<n;i++){
        ans^=(2*a[i]);
    }
    sort(a, a+n);
    ans^=self_psum_xor(a,n,30);
    cout<<ans<<endl;
}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    run();
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23