Submission #1113877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113877		vjudge1	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	908 ms	29316 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

// you'll be the best but now you're just trash

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n; cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return a[i] > a[j];
  });
  vector<int> pref(n + 1);
  vector<int> add(n);
  vector<int> nw(n);
  int res = 0;
  for (int b = 0; b < 30; ++b) {
    if (b) {
      int j = 0;
      for (int i : ord) {
        if (a[i] >> b - 1 & 1) {
          nw[j++] = i;
        }
      }
      for (int i : ord) {
        if (!(a[i] >> b - 1 & 1)) {
          nw[j++] = i;
        }
      }
      swap(ord, nw);
    }
    for (int i = 0; i < n; ++i) {
      pref[i + 1] = pref[i] + (a[ord[i]] >> b & 1);
    }
    long long cnt = 0, num = 0;
    for (int i = 0; i < n; ++i) {
      int k = add[i];
      int l0 = k - pref[k], l1 = pref[k], r0 = n - pref[n] - l0, r1 = pref[n] - l1;
      int c = a[i] >> b & 1;
      add[i] = 0;
      add[i] += ((1 - 1 - c - 0) < 0) * l0;
      add[i] += ((1 - 1 - c - 1) < 0) * l1;
      add[i] += ((1 - c - 0) < 0) * r0;
      add[i] += ((1 - c - 1) < 0) * r1;
      cnt += ((1 - c - 0) & 1) * l0;
      cnt += ((1 - c - 1) & 1) * l1;
      cnt += ((c - 0) & 1) * r0;
      cnt += ((c - 1) & 1) * r1;
      num += a[i] * 2 >> b & 1;
    }
    int x = ((cnt - num) / 2 + num) & 1;
    res += (x & 1) << b;
  }
  cout << res;
  return 0;
}

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:33:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   33 |         if (a[i] >> b - 1 & 1) {
      |                     ~~^~~
xorsum.cpp:38:25: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   38 |         if (!(a[i] >> b - 1 & 1)) {
      |                       ~~^~~

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