oj.uz

Submission #362934

# Submission time Handle Problem Language Result Execution time Memory
362934 2021-02-04T18:47:27 Z kiomi XOR Sum (info1cup17_xorsum) C++17
77 / 100
 666 ms 17664 KB 
//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define full(x,n) x,x+n+1
#define full(x) x.begin(),x.end()
#define finish return 0

#define putb push_back
#define f first
#define s second

//logx(a^n)=loga(a^n)/logx(a)
//logx(a*b)=logx(a)+logx(b)
//logx(y)=log(y)/log(x)
//logb(n)=loga(n)/loga(b)

#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define putf push_front
#define gainb pop_back

//(a+b)^n=sum of C(n,i)*a^i*b^(n-i) 0<=i<=n
//(a-b)^n=sum of C(n,i)*a^i*b^(n-i) for even i-for odd i

#define gainf pop_front
#define len(x) (int)x.size()

// 1/b%mod=b^(m-2)%mod
// (a>>x)&1==0
// a^b=(a+b)-2(a&b)

typedef double db;
typedef long long ll;

//sum of squares n*(n+1)*(2n+1)/6
//sum of cubes [n*(n+1)/2]^2
//sum of squares for odds n*(4*n*n-1)/3
//sum of cubes for odds n*n*(2*n*n-1)

const int ary=1e6+5;
const int mod=1e9+7;
const ll inf=1e18;

using namespace std;
using namespace __gnu_pbds;
int n,a[ary],c[ary],ans,cnt;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int b=28;b>=0;b--){
		int id=0;
		for(int i=1;i<=n;i++){
			if(((a[i]>>(b+1))&1)){
				a[i]-=(1<<(b+1));
			}
			else{
				id=i;
			}
		}
		int ip=id+1,ik=1,it=1;
		while(it<=n){
			if(ip>n){
				c[it]=a[ik];
				ik++;
			}
			else if(ik>id){
				c[it]=a[ip];
				ip++;
			}
			else if(a[ik]<=a[ip]){
				c[it]=a[ik];
				ik++;
			}
			else{
				c[it]=a[ip];
				ip++;
			}
			it++;
		}
		for(int i=1;i<=n;i++){
			a[i]=c[i];
		}
		cnt=0;
		int l=1,r=1;
		for(int i=n;i>=1;i--){
			if(a[i]+a[i]<(1<<b)||a[i]+a[1]>(1<<b)+(1<<b)-1){
				continue;
			}
			l=min(l,i);
			r=min(r,i);
			while(a[i]+a[l]<(1<<b)){
				l++;
			}
			while(r+1<=i&&a[i]+a[r+1]<=(1<<b)+(1<<b)-1){
				r++;
			}
			if(l<=r){
				cnt+=(r-l+1)%2;
				cnt%=2;
			}
		}
		l=1,r=1;
		for(int i=n;i>=1;i--){
			if(a[i]+a[i]<(1<<(b+1))+(1<<b)||a[i]+a[1]>(1<<(b+2))-1){
				continue;
			}
			l=min(l,i);
			r=min(r,i);
			while(a[i]+a[l]<(1<<(b+1))+(1<<b)){
				l++;
			}
			while(r+1<=i&&a[i]+a[r+1]<=(1<<(b+2))-1){
				r++;
			}
			if(l<=r){
				cnt+=(r-l+1)%2;
				cnt%=2;
			}
		}
		if(cnt){
			ans+=(1<<b);
		}
	}
	cout<<ans;
}

Compilation message

xorsum.cpp:7: warning: "full" redefined
    7 | #define full(x) x.begin(),x.end()
      | 
xorsum.cpp:6: note: this is the location of the previous definition
    6 | #define full(x,n) x,x+n+1
      |

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 8556 KB Output is correct
2 Correct 283 ms 9368 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 8556 KB Output is correct
2 Correct 283 ms 9368 KB Output is correct
3 Correct 433 ms 9836 KB Output is correct
4 Correct 422 ms 9508 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 75 ms 1516 KB Output is correct
4 Correct 66 ms 1516 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 328 ms 8556 KB Output is correct
4 Correct 283 ms 9368 KB Output is correct
5 Correct 433 ms 9836 KB Output is correct
6 Correct 422 ms 9508 KB Output is correct
7 Correct 75 ms 1516 KB Output is correct
8 Correct 66 ms 1516 KB Output is correct
9 Correct 629 ms 9836 KB Output is correct
10 Correct 666 ms 17516 KB Output is correct
11 Incorrect 652 ms 17664 KB Output isn't correct