제출 #1326810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326810		al95ireyiz	XOR Sum (info1cup17_xorsum)	C++20	45 / 100	185 ms	4276 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 5e5 + 5;
ll n, m, k = 0;

ll a[maxn], b[maxn];
void _() {
  // j-ci biti 1 olan pair sayini tapmaq ucun ele x, y cutlerini tapmaliyiq ki

  // 2 ^ j <= b[x] + b[y] < 2 ^ (j + 1) veya 
  // 2 ^ (j + 1) + 2 ^ j <= b[x] + b[y] < 2 ^ (j + 2)
  // harda ki b[i] = a[i] & (2 ^ (j + 1) - 1)

  cin >> n;
  for(ll i = 1; i <= n; i ++){
    cin >> a[i];
  }
  auto ok = [&](ll val, ll pw) -> bool{
    return pw <= val and val < (pw << 1);
  };
  auto ok2 = [&](ll val, ll pw) -> bool{
    return (pw << 1) + pw <= val and val < (pw << 2);
  };
  ll cv = 0;
  for(ll bt = 0; bt <= 30; bt ++){
    for(ll i = 1; i <= n; i ++){
      b[i] = a[i] & ((1ll << (bt + 1)) - 1);
    }

    sort(b + 1, b + n + 1);

    ll x_l, x_r, l, r, c = 0;

    // 2 ^ j <= b[x] + b[y] < 2 ^ (j + 1)
    l = 1ll << bt;
    r = 1ll << (bt + 1);
    
    x_l = x_r = 1;
    for(ll y = n; y >= 1; y --){
      while(b[x_l] + b[y] < l and x_l <= n) x_l ++;
      while(b[x_r] + b[y] < r and x_r <= n) x_r ++;

      c += max(0ll, x_r - max(x_l, y));
    }

    // 2 ^ (j + 1) + 2 ^ j <= b[x] + b[y] < 2 ^ (j + 2)
    l = (1ll << bt) + (1ll << (bt + 1));
    r = 1ll << (bt + 2);

    x_l = x_r = 1;
    for(ll y = n; y >= 1; y --){
      while(b[x_l] + b[y] < l and x_l <= n) x_l ++;
      while(b[x_r] + b[y] < r and x_r <= n) x_r ++;

      c += max(0ll, x_r - max(x_l, y));
    }

    if(c & 1) cv |= 1ll << bt;
  }
  cout << cv << '\n';
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  ll t = 1;
  // cin >> t;
  while(t --) _();
}

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