Cod sursa(job #2093022)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 22 decembrie 2017 19:41:04
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
# include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie{
    int poz;
    trie *next[2];
    trie(){
        next[0]=next[1]=NULL;
        poz=0;
    }
} *tata;
int s[100010],n,i,j,pozi,pozj,x,maxim;
void add(trie *nod,int val,int ii){
    if(ii==0){
        nod->poz=i;
        return;
    }
    int urm=((val&(1<<ii))>0);
    if(nod->next[urm]==NULL)
        nod->next[urm]=new trie;
    add(nod->next[urm],val,ii-1);
}
int poz(trie *nod,int val,int ii){
    if(ii==0)
        return nod->poz;
    int urm=1-((val&(1<<ii))>0);
    if(nod->next[urm]==NULL)
        urm=1-urm;
    return poz(nod->next[urm],val,ii-1);
}
int main () {
    fin>>n;
    tata=new trie;
    add(tata,0,20);
    for(i=1;i<=n;i++){
        fin>>x;
        s[i]=(s[i-1]^x);
        j=poz(tata,s[i],20);
        if((s[i]^s[j])>maxim){
            maxim=(s[i]^s[j]);
            pozi=i;
            pozj=j+1;
        }
        add(tata,s[i],20);
    }
    fout<<maxim<<" "<<pozj<<" "<<pozi<<"\n";
    return 0;
}