Submission #1312797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312797		neonglitch	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	1383 ms	29764 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 a[N],c[N],ord[N],n,pw=1;
int get(int L,int R)
{
	int i1=0,i=0,ans=0;
	// cout<<"We want "<<R<<endl;
	// cout<<"Array ";
	// for(int i=0;i<n;i++)cout<<a[ord[i]]&(pw-1)<<' ';
	// cout<<endl;
	while(i1+1<n and (a[ord[i1]]&(pw-1))+(a[ord[0]]&(pw-1))<L)
	{
		i1++;
	}
	i=i1;
	while(i+1<n and (a[ord[i]]&(pw-1))+(a[ord[0]]&(pw-1))<R)
	{
		i++;
	}

	for(int j=0;j<n;j++)
	{
		while(i>=0 and (a[ord[i]]&(pw-1))+(a[ord[j]]&(pw-1))>=R)
		{
			i--;
		}
		while(i1>=0 and (a[ord[i1]]&(pw-1))+(a[ord[j]]&(pw-1))>=L)
		{
			i1--;
		}
		ans+=(i-i1);
	}
	return ans;
}
int nxt[2][N],pto[3];
main()
{
	// int t=1;
	// cin>>t;
	// while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
			ord[i]=i;
		}
		int fnl=0;
		for(int j=0;j<31;j++)
		{
			pw<<=1;
			pto[0]=0;
			pto[1]=0;
			for(int i=0;i<n;i++)
			{
				bool pq=((a[ord[i]]&(pw>>1)));
				if(pq)
				{
					nxt[1][pto[1]++]=ord[i];
				}
				else{
					nxt[0][pto[0]++]=ord[i];
				}
			}
			int lpt=0;
			for(int i=0;i<pto[0];i++)ord[lpt++]=nxt[0][i];
			for(int i=0;i<pto[1];i++)ord[lpt++]=nxt[1][i];
			int on=get(pw>>1,pw);
			on += get(pw+(pw>>1),pw<<1);
			for(int i=0;i<n;i++)
			{
				int x=(a[(ord[i])]&(pw-1))<<1;
				if(x<pw and x>=(pw>>1))
				{
					on++;
				}
				if(x<(pw<<1) and x>=(pw+(pw>>1)))
				{
					on++;
				}
			}
			on>>=1;
			if(on&1)fnl+=(pw>>1);
		}
		cout<<fnl<<endl;
	}
}

Compilation message (stderr)

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

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