Submission #1273868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273868		anbg	XOR Sum (info1cup17_xorsum)	C++20	77 / 100	1695 ms	8260 KiB

xorsum

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e6 + 6;
int n, a[maxn], b[maxn];

void solve() {
  cin >> n;
  int lg = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    lg = max(lg, __lg(a[i]) + 1);
  }
  int res = 0;
  for (int bit = 0; bit <= lg; ++bit) {
    int t = (1 << bit);
    for (int i = 1; i <= n; ++i) {
      b[i] = a[i] % (t << 1);
    }
    sort(b + 1, b + n + 1);
    long long total = 0;
    int ptr = 0, sv = n + 1;
    for (int i = 1; i <= n; ++i) {
      if (b[i] >= t) {
        sv = i;
        break;
      }
    }
    for (int i = sv - 1; i > 0; --i) {
      if (ptr > i) break;
      while (ptr <= i and b[i] + b[ptr] < t) ++ptr;
      total += i - ptr + 1;
    }
    ptr = sv - 1;
    for (int i = sv; i <= n; ++i) {
      while (ptr > 0 and b[ptr] + b[i] >= (t << 1)) --ptr;
      total += ptr;
    }
    ptr = sv;
    for (int i = n; i >= sv; --i) {
      if (ptr > i) break;
      while (ptr <= i and b[i] + b[ptr] < (t << 1) + t) ++ptr;
      total += i - ptr + 1;
    }
    res ^= ((total & 1) << bit);
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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