제출 #362209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362209		keta_tsimakuridze	XOR Sum (info1cup17_xorsum)	C++14	0 / 100	1685 ms	69100 KiB

xorsum

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=4e5+5,mod=1e9+7,Mx=35e6+7;
int t,tree[2][Mx+7],a[N],n,k,i,j,cnt,ans,s[N],c[N];
void update(int ind,int val,int t){
	for(ind;ind<=Mx;ind+=ind&(-ind))
	tree[t][ind]+=val;
}
int  getans(int ind,int t){
	int pas=0;
	for(ind;ind>=1;ind-=ind&(-ind))
	pas+=tree[t][ind];
	return pas;
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(k=1;k<=n;k++){
		cin>>a[k];
	}
	for(k=1;k<=n;k++){
		s[k] = a[k]&1;
		cnt += c[s[k]^1];
		cnt%=2;
		c[s[k]]++;
		c[s[k]]%=2;
	}
	if(cnt%2) ans=1;
	for(i=1;i<25;i++){
		cnt = 0;
		
		for(k=1;k<=n;k++){
			//  
			int c = (a[k]&(1<<i)) > 0;
			cnt+=getans((1<<(i+1))-s[k],c)%2; if(cnt>=2) cnt-=2; 
			if(((1<<i)-s[k])>0) cnt=(cnt-getans(((1<<i)-s[k]),c)%2+2)%2; 	
			
			if(((1<<i)-s[k])>0) cnt=(cnt+getans(((1<<i)-s[k]),1^c)%2)%2;
			update(s[k]+1,1,c);  
		} //cout<<endl;
		for(k=1;k<=n;k++){
			int c = (a[k]&(1<<i)) > 0;
			update(s[k]+1,-1,c); 
			s[k]+=a[k]&(1<<i); 
		}
		if(cnt==1) ans+=1<<i; 
	}
	cout<<ans;
}

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

xorsum.cpp: In function 'void update(int, int, int)':
xorsum.cpp:8:6: warning: statement has no effect [-Wunused-value]
    8 |  for(ind;ind<=Mx;ind+=ind&(-ind))
      |      ^~~
xorsum.cpp: In function 'int getans(int, int)':
xorsum.cpp:13:6: warning: statement has no effect [-Wunused-value]
   13 |  for(ind;ind>=1;ind-=ind&(-ind))
      |      ^~~
xorsum.cpp: At global scope:
xorsum.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main(){
      |      ^

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