Cod sursa(job #723312)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 25 martie 2012 12:32:09
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>

using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");

int data[100100];
int trie[4858576];
bool avail_trie[4858576];
int n;

void insert(int val,int poz){
	int pozcurent=1,bit=1<<20;
	while(bit){
		pozcurent*=2;
		if(val&bit)
			pozcurent++;
		avail_trie[pozcurent]=true;
		bit/=2;
	}
	trie[pozcurent]=poz;
}

int find(int val){
	int copie=val,pozcurent=1,bit=1<<20,curent=0;
	while(bit){
		pozcurent<<=1;
		if(((val&bit)==0 && avail_trie[pozcurent+1]==true)||((val&bit)!=0 && avail_trie[pozcurent]==false) )
			pozcurent++;
		if(trie[pozcurent])
			curent=trie[pozcurent];
		bit>>=1;
	}
	return curent;
}

void read(){
	int i,x;
	in>>n;
	for(i=1;i<=n;++i){
		in>>x;
		data[i]=(data[i-1]^x);
	}
}


void solve(){
	int i,val=1,j,start,stop,xormax=0;
	for(i=0;i<=n;++i){
		j=find(data[i]);
		if((data[i]^data[j])>xormax){
			start=j+1;
			stop=i;
			if(start==stop)
				start--;
			xormax=(data[i]^data[j]);
		}
		insert(data[i],i);
	}
	if(start>stop){
		start^=stop;
		stop^=start;
		start^=stop;
	}
	out<<xormax<<" "<<start<<" "<<stop;
}

int main(){
	read();
	solve();
	return 0;
}