Submission #1146410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146410		Alihan_8	XOR Sum (info1cup17_xorsum)	C++20	0 / 100	1451 ms	24308 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

#define int 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++ ){
		int cnt = 0;
		
		array <int,2> t, p;
		
		t = p = {0, 0};
		
		for ( int i = 0; i < n; i++ ){
			int x = a[i] >> b & 1;
			
			cnt += t[x ^ 1];
			t[x] += 1; 
		}
		
		if ( b > 0 ){
			int freq = 0;
			
			for ( int i = 0; i < n; i++ ){
				int x = a[i] >> b & 1, y = a[i] >> (b - 1) & 1;
				
				if ( y != 0 ){
					freq += 1;
					cnt += freq;
					
					cnt -= p[x ^ 1] * 2;
					p[x] += 1;
				}
			}
		}
		
		vector <int> q;
		
		for ( auto &u: a ){
			if ( u >> b & 1 ) continue;
			
			q.push_back(u % (1 << b));
		}
		
		sort(q.begin(), q.end());
		
		int m = q.size(), j = m;
		
		for ( int i = 0; i < m; i++ ){
			if ( j <= i ) break;
			
			while ( j - 1 > i && q[j - 1] + q[i] >= (1 << b) ) --j;
			
			cnt += m - j;
		}
		
		ans |= (cnt & 1) << b;
	}
	
	cout << ans << '\n';
}

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