Submission #807186

#	Time	Username	Problem	Language	Result	Execution time	Memory
807186		Soumya1	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	1493 ms	21604 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;
  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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23