Submission #98552

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98552	2019-02-24T01:48:48 Z	luciocf	XOR (IZhO12_xor)	C++14	100 / 100	588 ms	58712 KB

xor

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5;

struct node
{
	node *b[2];
	int menor;

	node()
	{
		b[0] = b[1] = NULL;
		menor = 1e9+10;
	}
};

int n, x;
int num[maxn], p[maxn];

void insert(node *at, int v, int ind)
{
	for (int i = 30; i >= 0; i--)
	{
		bool d = (v&(1<<i));

		at->menor = min(at->menor, ind);

		if (!at->b[d]) at->b[d] = new node();

		at = at->b[d];
	}

	at->menor = min(at->menor, ind);
}

int query(node *at, int v)
{
	int ans = 0;

	for (int i = 30; i >= 0; i--)
	{
		if (!at) return -1;

		if (ans >= x) return at->menor;

		bool d = (v&(1<<i));

		if (d && at->b[0])
		{
			ans += (1<<i);
			at = at->b[0];
		}
		else if (d) at = at->b[1];

		if (!d && at->b[1])
		{
			ans += (1<<i);
			at = at->b[1];
		}
		else if (!d) at = at->b[0];
	}

	if (ans >= x) return at->menor;
	return -1;
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> x;

	node *root = new node();

	for (int i = 1; i <= n; i++)
	{
		cin >> num[i];

		p[i] = p[i-1]^num[i];
	}

	int ans = 0, ind;
	for (int i = 1; i <= n; i++)
	{
		insert(root, p[i-1], i-1);

		int pos = query(root, p[i]);
		if (pos == -1) continue;

		if (i-pos > ans)
		{
			ans = i-pos;
			ind = pos+1;
		}
	}
	
	cout << ind << " " << ans << "\n";
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:99:17: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << ind << " " << ans << "\n";
                 ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	19 ms	2048 KB	Output is correct
6	Correct	26 ms	2144 KB	Output is correct
7	Correct	25 ms	2176 KB	Output is correct
8	Correct	22 ms	2296 KB	Output is correct
9	Correct	203 ms	27624 KB	Output is correct
10	Correct	175 ms	27788 KB	Output is correct
11	Correct	175 ms	27640 KB	Output is correct
12	Correct	172 ms	27680 KB	Output is correct
13	Correct	174 ms	27640 KB	Output is correct
14	Correct	199 ms	27716 KB	Output is correct
15	Correct	182 ms	27740 KB	Output is correct
16	Correct	174 ms	27640 KB	Output is correct
17	Correct	570 ms	58616 KB	Output is correct
18	Correct	579 ms	58616 KB	Output is correct
19	Correct	539 ms	58616 KB	Output is correct
20	Correct	588 ms	58712 KB	Output is correct