Cod sursa(job #2533448)

Utilizator DanutAldeaDanut Aldea DanutAldea Data 29 ianuarie 2020 00:56:35
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

int n,m,i,j,v[100001],cnt,sol,st,dr;

struct trie{
    int poz;
    trie *f[2];

    trie(){
        f[0]=f[1]=NULL;
        poz=0;
    }
};
trie *r;

void ins(trie *r, int bit, int val, int poz){
    if(bit==-1){
        r->poz=poz;
        return;
    }

    bool x=(val>>bit)&1;
    if(r->f[x]==NULL)
        r->f[x]=new trie;
    ins(r->f[x],bit-1,val,poz);
}

int sea(trie *r, int bit, int val){
    if(bit==-1)
        return r->poz;

    bool x=(val>>bit)&1;
    if(r->f[!x]!=NULL)
        return sea(r->f[!x],bit-1,val);
    else
        return sea(r->f[x],bit-1,val);
}

int main(){
    fin>>n>>v[1];
    for(i=2;i<=n;i++){
        fin>>v[i];
        m=max(m,v[i]);
        v[i]=(v[i]^v[i-1]);
    }

    while(m){
        cnt++;
        m/=2;
    }

    r=new trie;
    ins(r,cnt,0,0);
    for(i=1;i<=n;i++){
        j=sea(r,cnt,v[i]);
        if((v[j]^v[i])>sol){
            sol=(v[j]^v[i]);
            st=j+1;
            dr=i;
        }
        ins(r,cnt,v[i],i);
    }

    fout<<sol<<" "<<st<<" "<<dr;

    return 0;
}