제출 #362934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362934		kiomi	XOR Sum (info1cup17_xorsum)	C++17	77 / 100	666 ms	17664 KiB

xorsum

//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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 0 / 23