Cod sursa(job #1254000)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 2 noiembrie 2014 01:27:44
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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;
}