Submission #807172

#	Time	Username	Problem	Language	Result	Execution time	Memory
807172		Soumya1	XOR Sum (info1cup17_xorsum)	C++17	45 / 100	1660 ms	12724 KiB

xorsum

#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
void testCase() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &i : a) cin >> i;
  int ans = 0;
  for (int bit = 0; bit < 30; bit++) {
    vector<int> b = a;
    for (int i = 0; i < n; i++) {
      b[i] %= (1 << (bit + 1));
    }
    sort(b.begin(), b.end());
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      int lo = (1 << bit), hi = (1 << (bit + 1)) - 1;
      int r = upper_bound(b.begin(), b.end(), hi - b[i]) - b.begin();
      int l = lower_bound(b.begin(), b.end(), lo - b[i]) - b.begin();
      if (l < i) l = i;
      cnt += max(0, r - l);
      lo = (1 << (bit + 1)) + (1 << bit), hi = (1 << (bit + 2)) - 1;
      r = upper_bound(b.begin(), b.end(), hi - b[i]) - b.begin();
      l = lower_bound(b.begin(), b.end(), lo - b[i]) - b.begin();
      if (l < i) l = i;
      cnt += max(0, r - l);
      cnt %= 2;
    }
    if (cnt & 1) ans ^= (1 << bit);
  }
  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

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