제출 #1172145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172145		fryingduc	XOR Sum (info1cup17_xorsum)	C++20	56 / 100	1658 ms	8264 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;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  int res = 0;
  for (int bit = 0; bit < 29; ++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: 0 / 21
• Subtask 4: 38 / 38
• Subtask 5: 0 / 23