Cod sursa(job #1376100)

Utilizator teoionescuIonescu Teodor teoionescu Data 5 martie 2015 15:58:45
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
const int Nmax = 100001;
struct tr{
    tr* t[2]; int h;
    tr(){t[0]=t[1]=NULL;h=0;}
} *root;
void update(int x,int &ind){
    tr* w=root; int p;
    for(int k=(1<<23);k;k>>=1){
        p=(x&k)>0;
        if(!w->t[p]) w->t[p]=new tr();
        w=w->t[p];
    }
    w->h=ind;
}
int query(int x){
    tr* w=root; int p;
    for(int k=(1<<23);k;k>>=1){
        p=(x&k)>0;
        if(w->t[!p]) w=w->t[!p];
        else w=w->t[p];
    }
    return w->h;
}
int N,v[Nmax],s[Nmax];
int main(){
    root=new tr();
    in>>N;
    for(int i=1;i<=N;i++) in>>v[i];
    for(int i=1;i<=N;i++) s[i]=s[i-1]^v[i];
    int i=1,y,b=s[1],st=1,dr=1; update(s[i],i);
    for(i=2;i<=N;i++){
        y=query(s[i]);
        if((s[i]^s[y])>b) b=(s[i]^s[y]),st=y+1,dr=i;
        update(s[i],i);
    }
    out<<b<<' '<<st<<' '<<dr<<'\n';
    return 0;
}