Submission #1312792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312792		neonglitch	XOR Sum (info1cup17_xorsum)	C++20	45 / 100	1693 ms	33972 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 R)
{
	int i=0,ans=0;
	// cout<<"We want "<<R<<endl;
	// cout<<"Array ";
	// for(int i=0;i<n;i++)cout<<a[ord[i]]%pw<<' ';
	// cout<<endl;
	while(i+1<n and (a[ord[i]]%pw)+(a[ord[0]]%pw)<R)
	{
		i++;
	}
	for(int j=0;j<n;j++)
	{
		while(i>=0 and (a[ord[i]]%pw)+(a[ord[j]]%pw)>=R)
		{
			i--;
		}
		// cout<<"two po "<<j<<' '<<i<<endl;
		ans+=(i+1);
	}
	// cout<<"answer "<<ans<<endl;
	// int cntp=0;
	// for(int i=0;i<n;i++)
	// {
		// cout<<"For "<<i<<' ';
		// for(int j=0;j<n;j++)
		// {
			// if((a[ord[i]]%pw)+(a[ord[j]]%pw) < R)
			// {
				// cout<<j<<' ';
				// cntp++;
			// }
		// }
		// cout<<endl;
	// }
	// cout<<"REAL "<<cntp<<endl;
	return ans;
}
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<32;j++)
		{
			pw*=2;
			vector<int> nxt[2]={};
			for(int i=0;i<n;i++)
			{
				nxt[((a[ord[i]]>>j)&1)].push_back(ord[i]);
			}
			int lpt=0;
			for(auto x:nxt[0])ord[lpt++]=x;
			for(auto x:nxt[1])ord[lpt++]=x;
			// cout<<"At "<<j<<endl;;
			// for(int i=0;i<n;i++)cout<<ord[i]<<' '<<(a[ord[i]]%pw)<<endl;
			// get(R) number of pairs with sum < R 
			int on=get(pw)-get(pw/2);
			// cout<<"fp "<<on<<endl;
			on += get(2*pw)-get(pw+(pw/2));
			// cout<<"sp "<<on<<endl;	
			for(int i=0;i<n;i++)
			{
				int x=(a[(ord[i])]%pw)*2;
				if(x<pw and x>=(pw/2))
				{
					on++;
				}
				if(x<2*pw and x>=(pw+(pw/2)))
				{
					on++;
				}
			}
			// cout<<"tp "<<on<<endl;
			on/=2;
			// cout<<"FNL "<<on<<endl;
			if(on&1)fnl+=pw/2;
		}
		cout<<fnl<<endl;
	}
}

Compilation message (stderr)

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

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