Submission #1146494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146494		Alihan_8	XOR Sum (info1cup17_xorsum)	C++20	56 / 100	1695 ms	12376 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

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];
		
		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: 0 / 21
• Subtask 4: 38 / 38
• Subtask 5: 0 / 23