Submission #365399

#	Time	Username	Problem	Language	Result	Execution time	Memory
365399		NurstanDuisengaliev	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	1102 ms	41540 KiB

xorsum

// Nurstan Duisengaliev(REALBOY)
// не, не надо меня узнавать 
#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3")                   
      
#include <bits/stdc++.h>
 
#define ll long long
#define all(x) x.begin(), x.end()
#define in insert
#define mp make_pair
#define F first
#define S second
#define ppf pop_front     	
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair <int, int>
#define pll pair <ll, ll>
#define boost() ios_base::sync_with_stdio(0), cin.tie(0)
#define sz(x) (int)x.size()
#define int ll

using namespace std;
 
const int N = (int)1e6 + 123;
const int mod = (int)1e9 + 7;
const ll INF = (ll)1e18 + 1;
int n, a[N], c[N]; 
void calc (int B) {
	if ((c[1] & (1 << B)) || !(c[n] & (1 << B))) return;
	int pos = 0;
	for (int i = 1; i <= n - 1; i ++) {
		if ((c[i] & (1 << B)) == 0 && (c[i + 1] & (1 << B))) {
			pos = i;
			break;	
		}
	}
	vector <int> f, s;
	for (int i = pos; i >= 1; i --) f.pb (c[i]);
	for (int i = n; i > pos; i --) s.pb (c[i] ^ (1 << B)); 
	int P = 1;
	while (sz (f) + sz (s)) {
		if (sz (f) == 0) {
			c[P] = s.back();
	   		s.ppb ();
	   	}
	   	else if (sz (s) == 0) {
	   		c[P] = f.back ();
	   		f.ppb ();
	   	}
	   	else {
	   		if (f.back () < s.back ()) {
	   			c[P] = f.back ();
	   			f.ppb ();
	   		}
	   		else {
	   			c[P] = s.back();
	   			s.ppb ();
	   		}
	   	}
		P ++;	
	}
	assert (P == n + 1);
	return;
}
void solve () {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		c[i] = a[i];
	}
	sort (c + 1, c + n + 1);
	ll ans = 0;	
	for (int B = 29; B >= 0; B --) {
		int r1 = n, l1 = n + 1, l2 = n + 1, r2 = n;
		ll sum = 0;
		for (int i = 1; i <= n; i ++) {
	    	while (r1 >= 1 && c[r1] + c[i] > (1 << (B + 1)) - 1) r1 --;
	    	while (l1 >= 2 && c[l1 - 1] + c[i] >= (1 << B)) l1 --;
	    	if (l1 <= min (i, r1)) sum += (min (i, r1) - l1 + 1);
	   		while (r2 >= 1 && c[r2] + c[i] > (1 << (B + 2)) - 1) r2 --;
	   		while (l2 >= 2 && c[l2 - 1] + c[i] >= (1 << B) + (1 << (B + 1))) l2 --;
	   		if (l2 <= min (i, r2)) sum += (min (i, r2) - l2 + 1);
		}  
		if (sum % 2 == 1) ans ^= (1 << B);
		calc (B);
	}
	cout << ans;
}   	
 
main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	boost ();
	int TT = 1;
//    cin >> TT;
	while (TT --) {
		solve ();
	}
	return 0;	                                    
}

Compilation message (stderr)

xorsum.cpp:95:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   95 | main () {
      |       ^

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