Submission #638860

#	Time	Username	Problem	Language	Result	Execution time	Memory
638860		MohamedAhmed04	XOR (IZhO12_xor)	C++14	100 / 100	114 ms	25292 KiB

xor

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 3e5 + 10 ;

int arr[MAX] ;
int n , x ;

int trie[MAX*30][2] , val[MAX*30] ;
int pref[MAX] ;

int id = 0 ;

void Insert(int idx)
{
	int node = 0 , y = pref[idx] ;
	for(int bit = 29 ; bit >= 0 ; --bit)
	{
		bool t = (y & (1 << bit)) ;
		if(!trie[node][t])
			trie[node][t] = ++id ;
		node = trie[node][t] ;
		if(!val[node])
			val[node] = idx ;
	}
	return ;
}

int query(int y)
{
	int node = 0 , ans = 1e9 ;
	for(int bit = 29 ; bit >= 0 ; --bit)
	{
		bool t = (y & (1 << bit)) , t2 = (x & (1 << bit)) ;
		if(t2)
		{
			if((!trie[node][!t]))
				return ans ;
			node = trie[node][!t] ;
		}
		else
		{
			if(trie[node][!t])
				ans = min(ans , val[trie[node][!t]]) ;
			if((!trie[node][t]))
				return ans ;
			node = trie[node][t] ;
		}
	}
	ans = min(ans , val[node]) ;
	return ans ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>x ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	Insert(0) ;
	for(int i = 1 ; i <= n ; ++i)
		pref[i] = pref[i-1] ^ arr[i] ;
	int idx = -1 , Max = -1 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		int j = query(pref[i]) ;
		if(i-j > Max)
			idx = j+1 , Max = i-j ;
		Insert(i) ;
	}
	return cout<<idx<<" "<<Max<<"\n" , 0 ;
}		

• Subtask 1: 100 / 100