oj.uz

Submission #850455

# Submission time Handle Problem Language Result Execution time Memory
850455 2023-09-16T15:04:14 Z AliHasanli XOR Sum (info1cup17_xorsum) C++17
0 / 100
 1600 ms 8292 KB 
#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;
  cin>>n;
    int A[n] ;
 for(int i=0;i<n;i++)
   cin>>A[i];
    int ans=xorOfSum(A, n);
    for(int i=0;i<n;i++ )
    {
        ans^=(A[i]*2);
    }
    cout<<ans;
    return 0;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1611 ms 8292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1611 ms 8292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -