Submission #1158163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158163		itaykarny	XOR Sum (info1cup17_xorsum)	C++20	45 / 100	1694 ms	25684 KiB

xorsum

#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC target("avx2,tune=native")

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;
using ll = long long;
using vll = vector<ll>;

const int MAX_N = 1e6 + 1;

void solve() {
    ll n;
    cin >> n;
    static ll arr[MAX_N];  // Use static array to avoid stack overflow
    for (ll i = 0; i < n; i++) cin >> arr[i];

    ll ans = 0;

    for (ll b = 0; b < 30; b++) {
        ll A = (1LL << b) - 1;
        vll cur0, cur1;

        for (ll i = 0; i < n; i++) {
            if ((arr[i] >> b) & 1)
                cur1.push_back(arr[i] & A);
            else
                cur0.push_back(arr[i] & A);
        }

        sort(cur0.begin(), cur0.end());
        sort(cur1.begin(), cur1.end());

        ll res = 0;
        ll carry = 1LL << b;

        for (ll i = 0; i < n; i++) {
            ll curVal = arr[i] & A;
            ll num0 = 0, num1 = 0;

            if (((2 * arr[i]) >> b) & 1) res++;

            if (((arr[i] >> b) & 1) == 0) {
                num0 = cur0.end() - lower_bound(cur0.begin(), cur0.end(), carry - curVal);
                num1 = lower_bound(cur1.begin(), cur1.end(), carry - curVal) - cur1.begin();
            }
            else {
                num0 = lower_bound(cur0.begin(), cur0.end(), carry - curVal) - cur0.begin();
                num1 = cur1.end() - lower_bound(cur1.begin(), cur1.end(), carry - curVal);
            }

            res += num0 + num1;
        }
        res /= 2;
        ans += (res % 2) * carry;
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();
}

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