Cod sursa(job #1202874)

Utilizator teoionescuIonescu Teodor teoionescu Data 29 iunie 2014 22:42:23
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
//#include"stdafx.h"
#include<fstream>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
const int Nmax = 100001;
int N,K,v[Nmax],msb;
struct trie{
	int pzero,punu,store;
	trie(){pzero=punu=store=0;}
	int is(int t){
		if(t==0) return pzero!=0;
		if(t==1) return punu!=0;
	}
	int next(int t){
		if(t==0){
			if(!pzero) return pzero=++K;
			return pzero;
		}
		if(t==1){
			if(!punu) return punu=++K;
			return punu;
		}
	}
} T[22*Nmax];
int main(){
	in>>N;
	for(int i=1;i<=N;i++) in>>v[i];
	for(int i=1;i<=N;i++) for(int k=0;(1<<k)<=v[i];k++) msb=max(msb,k);
	for(int i=2;i<=N;i++) v[i]=v[i]^v[i-1];
	int Ans=0,ast=1,adr=1;
	for(int i=1;i<=N;i++){
		int w=0,x=v[i];
		if(i>1){
			for(int k=msb;k>=0;k--){
				int bit = (((1<<k)&x)>0);
				if(T[w].is(!bit)) w=T[w].next(!bit);
				else w=T[w].next(bit);
			}
			int get=v[i]^v[T[w].store];
			if(get>Ans) Ans=get , ast=T[w].store+1 , adr=i;
			w=0;
		}
		for(int k=msb;k>=0;k--){
			int bit = (((1<<k)&x)>0);
			w=T[w].next(bit);
		}
		T[w].store=i;
	}
	out<<Ans<<' '<<ast<<' '<<adr<<'\n';
    return 0;
}