oj.uz

Submission #207545

# Submission time Handle Problem Language Result Execution time Memory
207545 2020-03-07T23:22:49 Z luciocf XOR Sum (info1cup17_xorsum) C++14
45 / 100
 1600 ms 8184 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 22 ms 376 KB Output is correct
2 Correct 22 ms 376 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1698 ms 8184 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 1698 ms 8184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 376 KB Output is correct
2 Correct 22 ms 376 KB Output is correct
3 Correct 589 ms 1192 KB Output is correct
4 Correct 584 ms 1272 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 376 KB Output is correct
2 Correct 22 ms 376 KB Output is correct
3 Execution timed out 1698 ms 8184 KB Time limit exceeded
4 Halted 0 ms 0 KB -