Cod sursa(job #304161)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 11 aprilie 2009 02:47:24
Problema Xor Max Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <iostream>
#include <algorithm>
#define FIN "xormax.in"
#define FOUT "xormax.out"
#define MAX 100010
using namespace std;
struct list{
	int inf;
	list *urm;
};
struct trie{
	list *term;
	trie *t[2];
} *T;
int N;
int sum[MAX];




void introduce(trie *T,int number,int pw,int term){

	if (pw<0) { list *q;q=new list;q->inf=term;q->urm=T->term;T->term=q;return;}
	if (number & (1<<pw)){

		if (T->t[1]==NULL){

			T->t[1]=new trie;
			T->t[1]->t[0]=NULL;
			T->t[1]->t[1]=NULL;
			T->t[1]->term=NULL;
		}
		introduce(T->t[1],number,pw-1,term);
	} else {

		if (T->t[0]==NULL){
			
			T->t[0]=new trie;
			T->t[0]->t[0]=NULL;
			T->t[0]->t[1]=NULL;
			T->t[0]->term=NULL;
		}
		introduce(T->t[0],number,pw-1,term);
	}
}

int smax(trie *T,int number,int pw,int care,int &inceput){

	if (pw<0){ 
		
		list *q=T->term;
		inceput=q->inf;
		q=q->urm;
		while (q){
			if (inceput>care){ if (q->inf<inceput){inceput=q->inf;}} else
				if (q->inf>inceput && q->inf<=care){ inceput=q->inf;}
			q=q->urm;
		}
	
	return 0;
	}
	int bit=number & (1<<pw);
	if (bit>0){bit=1;}
	if (T->t[1-bit]!=NULL){ return (1<<pw) + smax(T->t[1-bit],number,pw-1,care,inceput);} else 
	{return smax(T->t[bit],number,pw-1,care,inceput);}
}

int main(void){

	freopen(FIN,"rt",stdin);
	freopen(FOUT,"wt",stdout);

	scanf("%d",&N);
	sum[0]=0;
	int x;

	T=new trie;
	T->t[0]=NULL;
	T->t[1]=NULL;
	introduce(T,0,20,0);
	for (int i=1;i<=N;++i){
		scanf("%d",&x);
		sum[i]=sum[i-1]^x;
		introduce(T,sum[i],20,i);
	}

	int maxim=-1;
	int inceput;
	int maxstart,maxend;
	for (int i=1;i<=N;++i){

		int partsum=smax(T,sum[i],20,i,inceput);
		if (partsum>maxim){
			maxim=partsum;maxstart=inceput;maxend=i;
			if (maxstart>maxend){int aux=maxstart;maxstart=maxend;maxend=aux;}maxstart++;
		} else if (partsum==maxim){

			int cstart=inceput;
			int cend=i;
			if (cstart>cend){ int aux=cstart;cstart=cend;cend=aux;}
			cstart++;
			if (cend<maxend){
				maxend=cend;
				maxstart=cstart;
			} 
			else if (cend==maxend){
						if (cstart>maxstart){
							maxstart=cstart;
						}
			}
		}
	}

	printf("%d %d %d\n",maxim,maxstart,maxend);

	fclose(stdin);
	fclose(stdout);
	return 0;
}