Cod sursa(job #1254959)

Utilizator adnionutCojocaru Ionut adnionut Data 3 noiembrie 2014 20:19:19
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
/*
Punctaj final pe sursa curenta: 100p
*/
#include <fstream>
 
using namespace std;
 
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
 
int st,dr,xmax,i,n,x[100010];
 
struct trie {
    int poz;
    trie *b[2];
    trie(){
        poz=0;
        b[0]=b[1]=0;
    }
} *r=new trie;
 
void update(int b,trie *t,int poz,int a)
{
    if(b==-1){
        t->poz=poz;
        return;
    }
    if(t->b[((a&(1<<b))>0)]==NULL)
        t->b[((a&(1<<b))>0)]=new trie;
 
    update(b-1,t->b[((a&(1<<b))>0)],poz,a);
}
 
void query (int a, int b,trie *t ){
    if (b==-1){
        if ((a^x[t->poz])>xmax) {
            st=t->poz+1;
            dr=i;
            xmax=(a^x[t->poz]);
        }
        return;
    }
    if (t->b[1-((a&(1<<b))>0)]!=NULL){
        query (a,b-1,t->b[1-((a&(1<<b))>0)]);
        return;
    }
    query (a,b-1,t->b[((a&(1<<b))>0)]);
}
 
int main () {
 
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>x[i];
        x[i]=x[i-1]^x[i];
    }
    update (20,r,0,0);
    xmax=-1;
    for (i=1;i<=n;i++) {
        query(x[i],20,r);
        update (20,r,i,x[i]);
    }
 
    fout<<xmax<<" "<<st<<" "<<dr<<"\n";
 
    return 0;
}