oj.uz

Submission #207543

# Submission time Handle Problem Language Result Execution time Memory
207543 2020-03-07T23:18:08 Z luciocf XOR Sum (info1cup17_xorsum) C++14
0 / 100
 120 ms 3448 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5+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 <= 24; 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-1, i, (1<<b));
			int r = busca1(1, i-1, i, (1<<(b+1))-1);

			if (l != -1 && r != -1) qtd += (r-l+1);

			l = busca2(1, i-1, i, (1<<b) + (1<<(b+1)));
			r = busca1(1, i-1, 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 120 ms 3448 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 120 ms 3448 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -