Submission #1140206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140206		JelalTkm	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	863 ms	41704 KiB

xorsum

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1e5 + 100;
const int md = 1e9 + 7;
const int INF = 1e9;

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];

    int ans = 0;
    for (int k = 0; k < 31; k++) {
      vector<int> z, o, z1, o1;
      int pw = (1 << k);
      for (int i = 0; i < n; i++) {
        if (a[i] & pw) {
          o.push_back(a[i] % pw);
          o1.push_back(a[i]);
        }
        else {
          z.push_back(a[i] % pw);
          z1.push_back(a[i]);
        }
      }

      int p = 0;
      for (auto i : z1)
          a[p++] = i;
      for (auto i : o1)
          a[p++] = i;

      auto find_max = [&](vector<int> &a, vector<int> &b, bool t) {
        int sz = (int) b.size();
        vector<int> ok((int) a.size() + 1);
        int l = sz - 1, ans = 0, cnt = 0;
        for (int r = 0; r < (int) a.size(); r++) {
          while (l >= 0 && a[r] + b[l] >= pw) {
            if (t && l >= 0 && ok[l])
              cnt++;
            l--;
          }
          ans += sz - l - 1 - cnt;
          ok[r] = 1;
          if (t && ok[l + 1])
            cnt++;
        }

        return ans;
      };
      auto find_small = [&](vector<int> &a, vector<int> &b) {
        return (int) a.size() * (int) b.size() - find_max(a, b, false);
      };

      auto cnt00 = find_max(z, z, true);
      auto cnt11 = find_max(o, o, true);
      auto cnt01 = find_small(o, z);

      if ((cnt00 + cnt11 + cnt01) & 1)
        ans |= pw;
    }

    cout << ans << '\n';
  }
  return 0;
}

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