Submission #1312743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312743		neonglitch	XOR Sum (info1cup17_xorsum)	C++20	32 / 100	469 ms	23872 KiB

xorsum

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define int ll
const int N=1e6+2;
int cnt[N];
int get(int l)
{
	if(l<0)return 0;
	return cnt[min(l,N-1)];
}
main()
{
	int t=1;
	// cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		int a[n],c[n];
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
		int pw=1,fnl=0;
		for(int j=0;j<21;j++)
		{
			pw*=2;
			for(int i=0;i<N;i++)cnt[i]=0;
			for(int i=0;i<n;i++)c[i]=a[i]%pw,cnt[c[i]]++;
			for(int i=1;i<N;i++)cnt[i]+=cnt[i-1];
			
			int on=0;
			for(int i=0;i<n;i++)
			{
				for(int k=i;k<=i;k++)
				{
					int sx=(c[i]+c[k]);
					if((pw/2)<=sx and sx<pw)
					{
						on++;
					}
					if(pw+(pw/2)<=sx and sx<2*pw)
					{
						on++;
					}
				}
				// l <= c[i] + c[k]  < r
				// l-c[i] <= c[k]
				int l=pw/2,r=pw;
				on+=(get(r-c[i]-1)-get(l-c[i]-1));
				// on+=lower_bound(c,c+n,r-c[i])-lower_bound(c,c+n,l-c[i]);
				l=(l+r);
				r=(r+r);
				on+=(get(r-c[i]-1)-get(l-c[i]-1));
				// on+=lower_bound(c,cse+n,r-c[i])-lower_bound(c,c+n,l-c[i]);
				// c[k] < r-c[i]
			}
			on/=2;
			if(on&1)fnl+=pw/2;
		}
		cout<<fnl<<endl;
	}
}

Compilation message (stderr)

xorsum.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main()
      | ^~~~

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