oj.uz

Submission #1113877

# Submission time Handle Problem Language Result Execution time Memory
1113877 2024-11-17T17:03:42 Z vjudge1 XOR Sum (info1cup17_xorsum) C++17
100 / 100
 908 ms 29316 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 468 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 24648 KB Output is correct
2 Correct 379 ms 22856 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 24648 KB Output is correct
2 Correct 379 ms 22856 KB Output is correct
3 Correct 706 ms 26696 KB Output is correct
4 Correct 669 ms 25672 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 81 ms 3152 KB Output is correct
4 Correct 80 ms 3152 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 439 ms 24648 KB Output is correct
4 Correct 379 ms 22856 KB Output is correct
5 Correct 706 ms 26696 KB Output is correct
6 Correct 669 ms 25672 KB Output is correct
7 Correct 81 ms 3152 KB Output is correct
8 Correct 80 ms 3152 KB Output is correct
9 Correct 886 ms 29256 KB Output is correct
10 Correct 850 ms 29196 KB Output is correct
11 Correct 908 ms 29316 KB Output is correct