Submission #41689

#	Time	Username	Problem	Language	Result	Execution time	Memory
41689		MatheusLealV	XOR (IZhO12_xor)	C++14	100 / 100	292 ms	65788 KiB

xor

#include <bits/stdc++.h>
#define N 250005
#define logn 31
using namespace std;

int n, k, v[N], dp[N], ans;

struct node
{
	node *prox[2];

	int best;

	node() {prox[0] = prox[1] = NULL, best = 0;}
};

node *root;

inline void add(int num, int id, node *root)
{
   root->best = id;

   for(int i = logn; i >= 0; i--)
   {
      int bit = (num & (1<<i)) ? 1:0;

      if(!root->prox[bit]) root->prox[bit] = new node();

      root = root->prox[bit];

      root->best = id;
   }
}

inline int query(node *root, int x)
{
	for(int i = logn; i >= 0; i--)
	{
		int bit = (x & (1<<i)) ? 1:0;

		int aux = (k & (1<<i)) ? 1:0;

		if(aux)
		{
			if(!root->prox[!bit]) return -1;

			root = root->prox[!bit];
		}
		else
		{
			if(root->prox[!bit]) return root->prox[!bit]->best;

			root = root->prox[bit];
		}
	}

	return root->best;
}

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

	cin>>n>>k;

	root = new node();

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

		v[i] ^= v[i - 1];

		add(v[i], i, root);
	}

	for(int i = 1; i <= n; i++)
	{
		dp[i] = query(root, v[i - 1]);

		ans = max(ans, dp[i] - i + 1);
	}

	for(int i = 1; i <= n; i++) if(dp[i] - i + 1 == ans)
	{
		cout<<i<<" "<<ans<<"\n";

		return 0;
	}
}

• Subtask 1: 100 / 100