Submission #207624

#	Time	Username	Problem	Language	Result	Execution time	Memory
207624		AMnu	XOR Sum (info1cup17_xorsum)	C++14	0 / 100	638 ms	8696 KiB

xorsum

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

const int MAXN=4e5+5, LOG=25, MAXC=1<<LOG;

int N, H, X, Y, Z;
int A[MAXN];
bitset <MAXC> B;
bitset <MAXC> C;

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];
	}
	
	for (int i=0;i<LOG;i++) {
		X=1<<i;
		Y=X<<1;
		
		for (int j=0;j<X;j++) {
			B[j]=0;
			C[j]=0;
		}
		
		for (int j=0;j<N;j++) {
			Z=A[j]&(Y-1);
			C[Z]=C[Z]^B[Z];
			B[Z]=!B[Z];
		}
		
		if (!i) {
			H^=B[0]&B[1];
			continue;
		}
		
		Z=X>>1;
		
		for (int j=Y-1;j>=0;j--) {
			if (j&Z) {
				if (C[j]) {
					H^=X;
				}
			}
			
			B[j]=B[j]^B[j+1];
		}
		
		for (int j=Z;j<Y;j++) {
			if (B[j]^B[j+1]) {
				if (j&Z) {
					if (B[j]^B[X+((j&X)<<1)-j]) {
						H^=X;
					}
				}
				
				if (j&X) {
					if (B[0]^B[Y-j]) {
						H^=X;
					}
				}
			}
		}
	}
	
	cout<<H<<'\n';
	return 0;
}

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