Submission #207509

#	Time	Username	Problem	Language	Result	Execution time	Memory
207509		maximath_1	XOR Sum (info1cup17_xorsum)	C++11	100 / 100	906 ms	8312 KiB

xorsum

#include<bits/stdc++.h>
using namespace std;
 
/* data type and special numbers */
//#define int ll //use if ded
#define ll long long
#define ld long double
const ll inf=LLONG_MAX;
const ll mod=1e9+7;
const ld pi=acos(-1.0);
/* end data type and special numbers */
 
/* fast input.output */
#define gc getchar//_unlocked
#define pc putchar//_unlocked
#define endl pc('\n')
int get_i(){
	char c=gc(); bool neg=false;
	for(; c<'0'||'9'<c; c=gc())
		if(c=='-') neg=true;
	int rs=c-'0'; c=gc();
	for(; '0'<=c && c<='9'; c=gc())
		rs=(rs<<1)+(rs<<3)+(c-'0');
	if(neg) rs=-rs;
	return rs;
}
string get_s(){
	char c=gc();
	for(; c<33 && 126<c; c=gc());
	string s=""; s+=c; c=gc();
	for(; 33<=c && c<=126; c=gc())
		s+=c;
	return s;
}
char get_c(){
	char c=gc();
	for(; c<33 && 126<c; c=gc());
	return c;
}
void print_i(int _n){
	int N=_n, rev, count=0;
	rev=N;
	if(N==0) {pc('0'); return;}
	while((rev%10)==0) {count++; rev/=10;}
	rev=0;
	while(N!=0) {rev=(rev<<3)+(rev<<1)+N%10; N/=10;}
	while(rev!=0) {pc(rev%10+'0'); rev/=10;}
	while(count--) pc('0');
}
void print_s(string a){
	for(int i=0; i<a.size(); i++)
		pc(a[i]);
}
void print_c(char a){
	pc(a);
}
/* end fast input/output */
 
const int mxn=1000005;
int a[mxn], c[mxn];
int main(){
	int n=get_i(), ans=0;
	for(int i=0; i<n; i++) a[i]=get_i();
	for(int j=0; j<31; j++){
		int b=(1<<j), pt=0; long long cnt=0;
		if(j) for(int i=0; i<n; i++) if((a[i]|(1<<(j-1)))!=a[i]) c[pt++]=a[i];
		if(j) for(int i=0; i<n; i++) if((a[i]|(1<<(j-1)))==a[i]) c[pt++]=a[i];
		//sorting mod (1<<j)
		if(j) for(int i=0; i<n; i++) {a[i]=c[i]; c[i]=a[i]%b;}
		for(int i=0; i<n; i++) if((a[i]|b)==a[i]) cnt++;
		long long sum=0;
		int lf=0, rg=n-1;
		for(; lf<n; lf++){
			while(c[lf]+c[rg]>=b) rg--;
			sum+=(n-1)-rg;
		}
		for(int i=0; i<n; i++) if(2*c[i]>=b) sum++;
		if((sum/2+cnt*(n-cnt))%2==1) ans+=b;
	}
	print_i(ans); pc('\n');
}

Compilation message (stderr)

xorsum.cpp: In function 'void print_s(std::__cxx11::string)':
xorsum.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<a.size(); i++)
               ~^~~~~~~~~

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