oj.uz

Submission #413485

# Submission time Handle Problem Language Result Execution time Memory
413485 2021-05-28T19:18:18 Z KKT89 XOR Sum (info1cup17_xorsum) C++17
100 / 100
 827 ms 35012 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

const int MAXN=1e6+5;
pair<int,int> x[MAXN];
pair<int,int> for_sort[2][MAXN];
int sz[2];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i];
		x[i]={0,i};
	}
	int res=0;
	for(int bit=0;bit<30;bit++){
		auto Sort=[&](int bit)->void{
			sz[0]=sz[1]=0;
			for(int i=0;i<n;i++){
				if((1<<bit)&a[x[i].second]){
					x[i].first|=(1<<bit);
					for_sort[1][sz[1]++]=x[i];
				}
				else{
					for_sort[0][sz[0]++]=x[i];
				}
			}
			int id=0;
			for(int i=0;i<2;i++){
				for(int j=0;j<sz[i];j++){
					x[id++]=for_sort[i][j];
				}
			}
		};
		Sort(bit);
		int t=0;
		int v=(1<<bit);
		for(int i=n-1,j=0,k=0,l=0;i>=0;i--){
			j=min(j,i); k=min(k,i); l=min(l,i);
			while(j<i+1 and x[i].first+x[j].first<v)j++;
			while(k<i+1 and x[i].first+x[k].first<2*v)k++;
			while(l<i+1 and x[i].first+x[l].first<3*v)l++;
			t+=(k-j)+(n-l);
			t&=1;
		}
		if(t)res^=v;
	}
	cout << res << endl;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 26236 KB Output is correct
2 Correct 576 ms 24508 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 26236 KB Output is correct
2 Correct 576 ms 24508 KB Output is correct
3 Correct 685 ms 26044 KB Output is correct
4 Correct 645 ms 25296 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 464 KB Output is correct
3 Correct 74 ms 3240 KB Output is correct
4 Correct 76 ms 3320 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 464 KB Output is correct
3 Correct 632 ms 26236 KB Output is correct
4 Correct 576 ms 24508 KB Output is correct
5 Correct 685 ms 26044 KB Output is correct
6 Correct 645 ms 25296 KB Output is correct
7 Correct 74 ms 3240 KB Output is correct
8 Correct 76 ms 3320 KB Output is correct
9 Correct 777 ms 26116 KB Output is correct
10 Correct 786 ms 35012 KB Output is correct
11 Correct 827 ms 34996 KB Output is correct