oj.uz

Submission #807186

# Submission time Handle Problem Language Result Execution time Memory
807186 2023-08-04T14:34:07 Z Soumya1 XOR Sum (info1cup17_xorsum) C++17
100 / 100
 1493 ms 21604 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;
  vector<int> l(1 << 20);
  for (int bit = 0; bit < 30; bit++) {
    vector<int> b = a;
    for (int i = 0; i < n; i++) {
      b[i] %= (1 << (bit + 1));
    }
    if (bit > 19) {
      sort(b.begin(), b.end());
    } else {
      for (int i : b) l[i]++;
      b.clear();
      for (int i = 0; i < l.size(); i++) {
        while (l[i]) b.push_back(i), l[i]--;
      }
    }
    int cnt = 0;
    int lo = (1 << bit), hi = (1 << (bit + 1)) - 1;
    int l = n, r = n;
    for (int i = 0; i < n; i++) {
      while (r >= 1 && b[r - 1] > hi - b[i]) r--;
      while (l >= 1 && b[l - 1] >= lo - b[i] && (l - 1) >= i) l--;
      if (l < i) l = i;
      cnt += max(0, r - l);
      cnt %= 2;
    }
    lo = (1 << (bit + 1)) + (1 << bit), hi = (1 << (bit + 2)) - 1;
    l = n, r = n;
    for (int i = 0; i < n; i++) {
      while (r >= 1 && b[r - 1] > hi - b[i]) r--;
      while (l >= 1 && b[l - 1] >= lo - b[i] && (l - 1) >= i) l--;
      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;
}

Compilation message

xorsum.cpp: In function 'void testCase()':
xorsum.cpp:23:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |       for (int i = 0; i < l.size(); i++) {
      |                       ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4436 KB Output is correct
2 Correct 27 ms 4436 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 12264 KB Output is correct
2 Correct 940 ms 16020 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 12264 KB Output is correct
2 Correct 940 ms 16020 KB Output is correct
3 Correct 1311 ms 19116 KB Output is correct
4 Correct 1336 ms 18412 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4436 KB Output is correct
2 Correct 27 ms 4436 KB Output is correct
3 Correct 154 ms 5208 KB Output is correct
4 Correct 160 ms 5204 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4436 KB Output is correct
2 Correct 27 ms 4436 KB Output is correct
3 Correct 1004 ms 12264 KB Output is correct
4 Correct 940 ms 16020 KB Output is correct
5 Correct 1311 ms 19116 KB Output is correct
6 Correct 1336 ms 18412 KB Output is correct
7 Correct 154 ms 5208 KB Output is correct
8 Correct 160 ms 5204 KB Output is correct
9 Correct 1493 ms 21604 KB Output is correct
10 Correct 1420 ms 21596 KB Output is correct
11 Correct 1480 ms 21600 KB Output is correct