oj.uz

Submission #207509

# Submission time Handle Problem Language Result Execution time Memory
207509 2020-03-07T17:10:43 Z maximath_1 XOR Sum (info1cup17_xorsum) C++11
100 / 100
 906 ms 8312 KB 
#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

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.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 8192 KB Output is correct
2 Correct 477 ms 7800 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 8192 KB Output is correct
2 Correct 477 ms 7800 KB Output is correct
3 Correct 663 ms 8184 KB Output is correct
4 Correct 640 ms 7928 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 380 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 98 ms 1144 KB Output is correct
4 Correct 98 ms 1144 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 380 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 514 ms 8192 KB Output is correct
4 Correct 477 ms 7800 KB Output is correct
5 Correct 663 ms 8184 KB Output is correct
6 Correct 640 ms 7928 KB Output is correct
7 Correct 98 ms 1144 KB Output is correct
8 Correct 98 ms 1144 KB Output is correct
9 Correct 906 ms 8188 KB Output is correct
10 Correct 903 ms 8184 KB Output is correct
11 Correct 905 ms 8312 KB Output is correct