Submission #98550

#	Time	Username	Problem	Language	Result	Execution time	Memory
98550		luciocf	XOR (IZhO12_xor)	C++14	100 / 100	607 ms	60640 KiB

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 *Node, int v, int ind)
{
	node *at = Node;

	for (int i = 30; i >= 0; i--)
	{
		int d = (v&(1<<i)) > 0;

		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 *Node, int v)
{
	node *at = Node;
	int ans = 0;

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

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

		int d = (v&(1<<i)) > 0;

		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 (stderr)

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

• Subtask 1: 100 / 100