Cod sursa(job #1254945)

Utilizator lupuflaviu9lupuflaviu lupuflaviu9 Data 3 noiembrie 2014 19:53:12
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#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;
}