Submission #1146509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146509		Alihan_8	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	761 ms	45200 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n; cin >> n;
	
	vector <int> a(n);
	
	for ( auto &u: a ) cin >> u;
	
	int ans = 0;
	
	for ( int b = 0; b < 30; b++ ){
		array <int,2> cnt = {0, 0};
		
		vector <int> q;
		
		for ( auto &u: a ){
			q.push_back(u % (1 << b));
				
			cnt[u >> b & 1] ^= 1;
		}
		
		int x = cnt[0] * cnt[1];
		
		if ( b <= 23 ){
			int k = 1 << b;
			
			vector <int> pf(k + 1);
			
			for ( auto &u: q ) pf[u] += 1;
			
			for ( int i = 1; i <= k; i++ ) pf[i] += pf[i - 1];
			
			i64 tot = 0, z = 0;
			
			for ( auto &u: q ){
				int v = pf[k] - pf[k - u - 1];
				
				if ( u * 2 >= k ) z++;
				
				tot += v;
			} 
			
			tot = (tot - z) / 2 + z;
			
			x ^= tot & 1;
		} else{
			sort(q.begin(), q.end());
			
			int m = q.size(), j = m;
			
			for ( int i = 0; i < m; i++ ){
				while ( j - 1 >= 0 && q[j - 1] + q[i] >= (1 << b) ) --j;
				
				x ^= (m - max(i, j)) & 1;
			}
		}
		
		ans |= x << b;
	}
	
	cout << ans << '\n';
}

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