Submission #389474

#	Time	Username	Problem	Language	Result	Execution time	Memory
389474		Kevin_Zhang_TW	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	430 ms	12168 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 1000010, MAX_B = 35;

#define int ll

int n, a[MAX_N], cnt[MAX_B];

ll sum(ll l, ll r) { return (l + r) * (r - l + 1) / 2; }

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0;i < n;++i)
		cin >> a[i];
	sort(a, a + n);

	for (int b = 30;b >= 0;--b) {
		if (~a[n-1]>>b&1) continue;

		int M = 0;
		while (M < n && (~a[M]>>b&1)) ++M;

		debug(a, a + n);

		for (int i = M;i < n;++i) a[i] ^= 1ll<<b;
		
		
		ll val = 1ll << b;

		ll x = 0;

		for (int i = 0, j = n-1;i < M;++i) {
			while (j >= M && a[i] + a[j] >= val)
				--j;
			x += j - M + 1;
		}
		//  0s,   1s
		ll A = M, B = n - M;

		cnt[b + 1] ^= (sum(1, B)) + A * B - x;

		cnt[b] ^= (A * B);

		inplace_merge(a, a + M, a + n);
	}

	int res = 0;

	for (int i = 0;i <= 30;++i) if (cnt[i] & 1) {
		res |= 1ll << i;
	}

	cout << res << '\n';
}

Compilation message (stderr)

xorsum.cpp: In function 'int32_t main()':
xorsum.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
xorsum.cpp:39:3: note: in expansion of macro 'debug'
   39 |   debug(a, a + n);
      |   ^~~~~

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