Submission #207625

#	Time	Username	Problem	Language	Result	Execution time	Memory
207625		AMnu	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	756 ms	9140 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e6+5, LOG=30, INF=2e9;

int N, H;
int X, Y, Z;
int a, b, c;
int A[MAXN];
int B[MAXN];

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin>>N;
	
	for (int i=0;i<N;i++) {
		cin>>A[i];
	}
	
	sort(A,A+N);
	A[N]=INF;
	B[N]=INF;
	
	for (int i=LOG-1;i>=0;i--) {
		X=1<<i;
		Y=X<<1;
		Z=X>>1;
		
		a=0;
		b=N;
		
		for (int j=N-1;j>=0;j--) {
			if (A[j]>=Y) {
				A[j]-=Y;
				b=j;
			}
			
			B[j]=A[j];
		}
		
		c=b;
		
		for (int j=0;j<N;j++) {
			if (a<c&&B[a]<B[b]) {
				A[j]=B[a];
				a++;
			}
			else {
				A[j]=B[b];
				b++;
			}
		}
		
		a=N;
		b=N;
		c=N;
		
		for (int j=0;j<N;j++,a++,b++,c++) {
			while (a>j&&A[a-1]>=X-A[j]) {
				a--;
			}
			
			while (b>j&&A[b-1]>=Y-A[j]) {
				b--;
			}
			
			while (c>j&&A[c-1]>=X+Y-A[j]) {
				c--;
			}
			
			if ((N^a^b^c)&1) {
				H^=X;
			}
		}
	}
	
	cout<<H<<'\n';
	return 0;
}

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