Submission #1315869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315869		penguin133	XOR Sum (info1cup17_xorsum)	C++20	45 / 100	1695 ms	12332 KiB

xorsum

// Source: https://usaco.guide/general/io

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

int n, a[1000005];

int main() {
	cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 0; i < 30; i++) {
        vector <int> v;
        int mx = 0;
        for (int j = 1; j <= n; j++) {
          int x = a[j] % (1ll<<(i + 1));
          mx = max(mx, a[j]);
            v.push_back(x);
        }
        if (i && mx < (1ll<<(i - 1))) break;
        sort(v.begin(), v.end());
        long long tmp = 0, tmp2 = 0;
        for (int j = 1; j <= n; j++) {
            int x = a[j] % (1ll<<(i + 1));
            int l = (1ll<<i) - x, r = (1ll<<(i + 1)) - 1 - x;
            if(l >= 0) {
                tmp += upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
                if (l <= x && x <= r) tmp--, tmp2++;
            }
            else {
                tmp += v.end() - lower_bound(v.begin(), v.end(), l + (1ll<<(i + 1)));
                tmp += upper_bound(v.begin(), v.end(), r) - v.begin();
                if (x <= r || x >= l + (1ll<<(i + 1))) tmp--, tmp2++;
            }
            //cout << tmp << ' ';
        }
        tmp /= 2; tmp += tmp2;
        //cout << tmp << '\n';
        //tmp /= 2;
        if (tmp & 1) ans ^= (1ll<<i);
    }
    cout << ans;
}

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