Submission #41611

#	Time	Username	Problem	Language	Result	Execution time	Memory
41611		MatheusLealV	XOR (IZhO12_xor)	C++14	0 / 100	2052 ms	262144 KiB

xor

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

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

struct node
{
	node *prox[2];

	int num, qtd;

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

node *version[N];

inline void add(int num, node *prev, node *root)
{
   root->qtd = prev->qtd + 1;

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

      if(mask)
      {
         root->prox[1] = new node;
       
         if(prev != NULL) root->prox[0] = prev->prox[0];
      }
      else
      {
         root->prox[0] = new node;
       
         if(prev != NULL) root->prox[1] = prev->prox[1];
      }

      root = (mask) ? root->prox[1] : root->prox[0];

      if(prev != NULL) prev = (mask) ? prev->prox[1] : prev->prox[0];

      root->qtd = 1;
      
      if(prev != NULL) root->qtd += prev->qtd;
   }
}

inline bool check(node *root, int x)
{
	int y = 0;
 
	for(int i = logn; i >= 0; i --)
	{
		bool bit = (x & (1<<i));
 
		if(root->prox[!bit])
		{
			y += (1<<i);

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

		else root = root->prox[bit];
	}
 
	return y >= k;
}

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

	cin>>n>>k;

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

	version[0] = new node();

	node *root = version[0];

	for(int i = logn; i >= 0; i--)
	{
		root->prox[0] = new node();

		root = root->prox[0];
	}

	for(int i = 1; i <= n; i++)
	{
		version[i] = new node();

		add(v[i], version[i - 1], version[i]);
	}

	for(int i = 1; i <= n; i++)
	{
		int ini = 1, fim = i, mid, best = -1;

		while(fim >= ini)
		{
			mid = (ini + fim)/2;

			if(check(version[mid - 1], v[i]))
			{
				dp[mid] = max(dp[mid], i);

				fim = mid - 1;
			}

			else ini = mid + 1;
		}
	}

	int ans = 0;

	for(int i = 1; i <= n; i++) ans = max(ans, dp[i] - i);

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

		return 0;
	}
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:99:30: warning: unused variable 'best' [-Wunused-variable]
   int ini = 1, fim = i, mid, best = -1;
                              ^

• Subtask 1: 0 / 100