oj.uz

Submission #389474

# Submission time Handle Problem Language Result Execution time Memory
389474 2021-04-14T06:34:43 Z Kevin_Zhang_TW XOR Sum (info1cup17_xorsum) C++17
100 / 100
 430 ms 12168 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 12000 KB Output is correct
2 Correct 179 ms 11244 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 12000 KB Output is correct
2 Correct 179 ms 11244 KB Output is correct
3 Correct 293 ms 12168 KB Output is correct
4 Correct 299 ms 11580 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 43 ms 1424 KB Output is correct
4 Correct 44 ms 1512 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 193 ms 12000 KB Output is correct
4 Correct 179 ms 11244 KB Output is correct
5 Correct 293 ms 12168 KB Output is correct
6 Correct 299 ms 11580 KB Output is correct
7 Correct 43 ms 1424 KB Output is correct
8 Correct 44 ms 1512 KB Output is correct
9 Correct 430 ms 12020 KB Output is correct
10 Correct 422 ms 12044 KB Output is correct
11 Correct 419 ms 11964 KB Output is correct