Cod sursa(job #508642)

Utilizator mare95Mare Adrian Sorin mare95 Data 9 decembrie 2010 11:52:10
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
/*
 * File:   main.cpp
 * Author: petru
 *
 * Created on 2010-11-20
 */


#include <cstdio>
#define deb(n) fprintf(stderr,"%d ",(n));
#define debnl fprintf(stderr,"n");
#define BIT(n, i) ((n >> i) & 1)

int n;

struct trie{
    int nr;
    trie *urm[2];
    trie() {
        urm[0]=urm[1]=NULL;
        nr=0;
    }
} *t=new trie;

void insert(trie *t,int val, int poz, int a) {
    if(0>a) {
        t->nr=poz;
        return;
    }
    int x=(bool)BIT(val,a);
    if(NULL==t->urm[x]) t->urm[x]=new trie;
    insert(t->urm[x],val-(1<<a)*x,poz,a-1);
}

int find(trie *t, int &rez,int y,int a) {
    if(0>a) return t->nr;
    int x=!(BIT(y,a));
    if(NULL!=t->urm[x]) {
        rez+=(1<<a)*x;
        return find(t->urm[x],rez,y,a-1);
    }
    rez+=(1<<a)*(!x);
    return find(t->urm[!x],rez,y,a-1);
}

int main()
{
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    int y=0,x,ifin,jfin,xorm,poz;
    for(int i=1; i<=n; ++i) {
        scanf("%d",&x);
        y^=x;
        insert(t,y,i,20);
        if(1==i) {
            xorm=y;
            ifin=0;
            jfin=1;
            continue;
        }
        x=0;
        poz=find(t,x,y,20);
        if((x^y)>xorm) {
            xorm=x^y;
            ifin=poz;
            jfin=i;
        }
    }
    printf("%d %d %d",xorm,ifin+1,jfin);
	return 0;
}