Submission #638860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
638860	2022-09-07T17:48:52 Z	MohamedAhmed04	XOR (IZhO12_xor)	C++14	100 / 100	114 ms	25292 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	5 ms	1108 KB	Output is correct
6	Correct	6 ms	1308 KB	Output is correct
7	Correct	6 ms	1236 KB	Output is correct
8	Correct	8 ms	1352 KB	Output is correct
9	Correct	40 ms	11856 KB	Output is correct
10	Correct	36 ms	11820 KB	Output is correct
11	Correct	37 ms	11768 KB	Output is correct
12	Correct	33 ms	11724 KB	Output is correct
13	Correct	34 ms	11724 KB	Output is correct
14	Correct	41 ms	11800 KB	Output is correct
15	Correct	36 ms	11724 KB	Output is correct
16	Correct	43 ms	11704 KB	Output is correct
17	Correct	114 ms	25220 KB	Output is correct
18	Correct	96 ms	25232 KB	Output is correct
19	Correct	98 ms	25292 KB	Output is correct
20	Correct	107 ms	25172 KB	Output is correct