Submission #850448

#	Time	Username	Problem	Language	Result	Execution time	Memory
850448		AliHasanli	XOR Sum (info1cup17_xorsum)	C++17	0 / 100	0 ms	348 KiB

xorsum

#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find XOR of pairwise
// sum of every unordered pairs
int xorOfSum(int a[], int n)
{
 
    int i, j, k;
     
    // Sort the array
    sort(a, a + n);
 
    int ans = 0;
 
    // Array elements are not greater
    // than 1e7 so 27 bits are suffice
    for (k = 0; k < 27; ++k) {
         
        // Modded elements of array
        vector<int> b(n);
         
        // Loop to find the modded
        // elements of array
        for (i = 0; i < n; i++)
            b[i] = a[i] % (1 << (k + 1));
 
        // Sort the modded array
        sort(b.begin(), b.end());
 
        int cnt = 0;
        for (i = 0; i < n; i++) {
            // finding the bound for j
            // for given i using binary search
            int l = lower_bound(b.begin() +
                           i + 1, b.end(),
               (1 << k) - b[i]) - b.begin();
            int r = lower_bound(b.begin() +
                    i + 1, b.end(), (1 << (k + 1)) -
                          b[i]) - b.begin();
 
            // All the numbers in the range
            // of indices can be added to the
            // count to check the xor.
            cnt += r - l;
 
            l = lower_bound(b.begin() + i + 1,
                 b.end(), (1 << (k + 1)) +
                 (1 << k) - b[i]) - b.begin();
            cnt += n - l;
        }
        // Remainder of cnt * kth power
        // of 2 added to the xor value
        ans += (cnt % 2) * 1LL * (1 << k);
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int n = 3;
    int A[n] = { 1, 2, 3 };
 
    cout << xorOfSum(A, n);
    return 0;
}

Compilation message (stderr)

xorsum.cpp: In function 'int xorOfSum(int*, int)':
xorsum.cpp:10:12: warning: unused variable 'j' [-Wunused-variable]
   10 |     int i, j, k;
      |            ^

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