Submission #207545

#	Time	Username	Problem	Language	Result	Execution time	Memory
207545		luciocf	XOR Sum (info1cup17_xorsum)	C++14	45 / 100	1698 ms	8184 KiB

xorsum

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 1e6+10;
 
int a[maxn];
int v[maxn];
 
int busca1(int l, int r, int pos, int x)
{
	int ini = l, fim = r, ans = -1;
 
	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;
 
		if (a[mid] + a[pos] <= x) ans = mid, ini = mid+1;
		else fim = mid-1;
	}
 
	return ans;
}
 
int busca2(int l, int r, int pos, int x)
{
	int ini = l, fim = r, ans = -1;
 
	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;
 
		if (a[mid] + a[pos] >= x) ans = mid, fim = mid-1;
		else ini = mid+1;
	}
 
	return ans;
}
 
int main(void)
{
	int n;
	scanf("%d", &n);
 
	for (int i = 1; i <= n; i++)
		scanf("%d", &v[i]);
 
	int ans = 0;
 
	for (int b = 0; b <= 30; b++)
	{
		int qtd = 0;
 
		for (int i = 1; i <= n; i++)
			a[i] = v[i]%(1<<(b+1));
 
		sort(a+1, a+n+1);
 
		for (int i = 1; i <= n; i++)
		{
			int l = busca2(1, i, i, (1<<b));
			int r = busca1(1, i, i, (1<<(b+1))-1);
 
			if (l != -1 && r != -1) qtd += (r-l+1);
 
			l = busca2(1, i, i, (1<<b) + (1<<(b+1)));
			r = busca1(1, i, i, (1<<(b+2))-2);
 
			if (l != -1 && r != -1) qtd += (r-l+1);
		}
 
		if (qtd%2) ans += (1<<b);
	}
 
	printf("%d\n", ans);
}

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
xorsum.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i]);
   ~~~~~^~~~~~~~~~~~~

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