Submission #1146701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146701		crispxx	XOR Sum (info1cup17_xorsum)	C++20	0 / 100	1695 ms	8168 KiB

xorsum

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

typedef long long ll;

int computeXorPairwiseSum(vector<int>& V) {
    int N = V.size();
    int result = 0;
    
    for (int bit = 0; bit < 29; bit++) {
        int mask = (1 << (bit + 1)) - 1;  // Mask for last (bit+1) bits
        
        vector<int> modVals(N);
        for (int i = 0; i < N; i++) {
            modVals[i] = V[i] & mask;  // Take only last (bit+1) bits
        }
        
        sort(modVals.begin(), modVals.end());
        
        ll count = 0;
        
        for (int i = 0; i < N; i++) {
            int low1 = (1 << bit) - modVals[i];
            int high1 = (1 << (bit + 1)) - 1 - modVals[i];
            int low2 = (1 << (bit + 1)) + (1 << bit) - modVals[i];
            int high2 = (1 << (bit + 2)) - 2 - modVals[i];
            
            count += lower_bound(modVals.begin(), modVals.end(), high1 + 1) - lower_bound(modVals.begin(), modVals.end(), low1);
            count += lower_bound(modVals.begin(), modVals.end(), high2 + 1) - lower_bound(modVals.begin(), modVals.end(), low2);
            
            // Remove self pair contribution
            if ((modVals[i] * 2) & (1 << bit)) {
                count--;
            }
        }
        
        count /= 2;  // Each pair is counted twice
        
        if (count % 2 == 1) {
            result |= (1 << bit);
        }
    }
    
    return result;
}

int main() {
    int N;
    cin >> N;
    vector<int> V(N);
    for (int i = 0; i < N; i++) {
        cin >> V[i];
    }
    cout << computeXorPairwiseSum(V) << endl;
    return 0;
}

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