Cod sursa(job #307330)

Utilizator BabanuBarbieru Irineu Babanu Data 23 aprilie 2009 22:29:54
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.9 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{   
    int term;   
    trie *t[2];   
} *T;   
int N;   
int sum[MAX];   
  
  
  
  
void introduce(trie *T,int number,int pw,int term){   
  
    if (pw<0) { if (T->term==-1){T->term=term;}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=-1;   
        }   
        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=-1;   
        }   
        introduce(T->t[0],number,pw-1,term);   
    }   
}   
  
int smax(trie *T,int number,int pw,int care,int &inceput){   
  
    if (pw<0){    
        inceput=T->term;   
       
    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;}   
            if (maxstart==maxend){++maxend;} else {++maxstart;}   
        } else if (partsum==maxim){   
  
            int cstart=inceput;   
            int cend=i;   
            if (cstart>=cend){ int aux=cstart;cstart=cend;cend=aux;}   
            if (cstart==cend){++cend;} else {++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;   
}  
#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{
	int term;
	trie *t[2];
} *T;
int N;
int sum[MAX];




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

	if (pw<0) { if (T->term==-1){T->term=term;}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=-1;
		}
		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=-1;
		}
		introduce(T->t[0],number,pw-1,term);
	}
}

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

	if (pw<0){ 
		inceput=T->term;
	
	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;}
			if (maxstart==maxend){++maxend;} else {++maxstart;}
		} else if (partsum==maxim){

			int cstart=inceput;
			int cend=i;
			if (cstart>=cend){ int aux=cstart;cstart=cend;cend=aux;}
			if (cstart==cend){++cend;} else {++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;
}