oj.uz

Submission #362210

# Submission time Handle Problem Language Result Execution time Memory
362210 2021-02-02T06:13:58 Z keta_tsimakuridze XOR Sum (info1cup17_xorsum) C++14
0 / 100
 1600 ms 68972 KB 
#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; 
	}
	for(k=1;k<=n;k++){
		ans^=a[k]*2;
	}
	cout<<ans;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 68972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1694 ms 6124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1694 ms 6124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 68972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 68972 KB Output isn't correct
2 Halted 0 ms 0 KB -