oj.uz

Submission #807172

# Submission time Handle Problem Language Result Execution time Memory
807172 2023-08-04T14:25:17 Z Soumya1 XOR Sum (info1cup17_xorsum) C++17
45 / 100
 1600 ms 12724 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 336 KB Output is correct
2 Correct 15 ms 396 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1660 ms 12724 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 1660 ms 12724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 336 KB Output is correct
2 Correct 15 ms 396 KB Output is correct
3 Correct 408 ms 2004 KB Output is correct
4 Correct 423 ms 2004 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 336 KB Output is correct
2 Correct 15 ms 396 KB Output is correct
3 Execution timed out 1660 ms 12724 KB Time limit exceeded
4 Halted 0 ms 0 KB -