Cod sursa(job #1625288)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 2 martie 2016 17:59:25
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
// Template v2
#define pb push_back
#define mp make_pair
#define first x
#define second y
#define l(x) x<<1
#define r(x) x<<1 | 1
#include<math.h>
#include<fstream>

using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");

struct Trie{
	int k,val;
	Trie* next[3];
	Trie()
	{
		k=0, val=0;
		for(int i=0; i<3; ++i)
			next[i]=NULL;
	}
};

Trie* R=new Trie;

int s,l,val,n,c,rsl,rsr;
int xormax=0;

void insert(int c)
{
	bool q;
	Trie* node = R;
	for(int i=29; i>=0; --i)
	{
		q=false;
		if(c&(1<<i))
			q=true;
		
		//cout<<q;
		if(node->next[q] == NULL)
			node->next[q] = new Trie;
		node=node->next[q];
	}
	node->k=l;
	node->val=c;
	//cout<<"\n";
}

void search(int c)
{
	bool q;
	Trie* node = R;
	for(int i=29; i>=0; --i){
		q=true;
		if(c&(1<<i))
			q=false;
		
		if(node->next[q] == NULL)
			q=!q;
			
		node=node->next[q];
	}
	
	l=node->k;
	val=node->val;
}

void read()
{
	
	s=-1;
	cin>>n;
	xormax=-1;
	for(int i=1; i<=n; ++i)
	{
		cin>>c;
		if(s==-1)
			s=c;
		else
			s=s^c;
		if(xormax==-1)
		{
			xormax=c;
			rsl=0;
			rsr=1;
		}
		l=i;
		
		insert(s);
		search(s);
		
		if((val^s) > xormax)
		{
			xormax=val^s;
			rsl=l;
			rsr=i;
		}
		
		//cout<<i<<" "<<l<<" "<<val<<" "<<(val^s)<<"\n";
	}
	cout<<xormax<<" "<<rsl+1<<" "<<rsr<<"\n";
	
}

int main() {
    read();

    return 0;
}