Submission #134578

#	Time	Username	Problem	Language	Result	Execution time	Memory
134578		mohammedehab2002	XOR (IZhO12_xor)	C++11	100 / 100	203 ms	23416 KiB

xor

#include <iostream>
using namespace std;
int l,trie[10000000][2],mn[10000000],cn;
void insert(int x,int idx)
{
	int cur=0;
	for (int i=29;i>=0;i--)
	{
		bool b=(x&(1<<i));
		if (!trie[cur][b])
		{
			trie[cur][b]=++cn;
			mn[cn]=idx;
		}
		cur=trie[cur][b];
		mn[cur]=min(mn[cur],idx);
	}
}
int get(int x)
{
	int cur=0,ans=1e9;
	for (int i=29;i>=0;i--)
	{
		bool b=(x&(1<<i)),b2=(l&(1<<i));
		if (!b2 && trie[cur][!b])
		ans=min(ans,mn[trie[cur][!b]]);
		b^=b2;
		if (!trie[cur][b])
		break;
		cur=trie[cur][b];
	}
	return ans;
}
int main()
{
	int n,cum=0,k=-1,idx;
	scanf("%d%d",&n,&l);
	l--;
	for (int i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		insert(cum,i-1);
		cum^=a;
		int tmp=get(cum);
		if (i-tmp>k)
		{
			k=i-tmp;
			idx=tmp+1;
		}
	}
	printf("%d %d",idx,k);
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&l);
  ~~~~~^~~~~~~~~~~~~~
xor.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a);
   ~~~~~^~~~~~~~~

• Subtask 1: 100 / 100