oj.uz

Submission #207625

# Submission time Handle Problem Language Result Execution time Memory
207625 2020-03-08T07:25:58 Z AMnu XOR Sum (info1cup17_xorsum) C++14
100 / 100
 756 ms 9140 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 8160 KB Output is correct
2 Correct 429 ms 8568 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 8160 KB Output is correct
2 Correct 429 ms 8568 KB Output is correct
3 Correct 588 ms 8932 KB Output is correct
4 Correct 537 ms 8696 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 79 ms 2040 KB Output is correct
4 Correct 79 ms 1912 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 494 ms 8160 KB Output is correct
4 Correct 429 ms 8568 KB Output is correct
5 Correct 588 ms 8932 KB Output is correct
6 Correct 537 ms 8696 KB Output is correct
7 Correct 79 ms 2040 KB Output is correct
8 Correct 79 ms 1912 KB Output is correct
9 Correct 708 ms 9140 KB Output is correct
10 Correct 756 ms 8940 KB Output is correct
11 Correct 697 ms 8944 KB Output is correct