Cod sursa(job #2533961)

Utilizator Raresr14Rosca Rares Raresr14 Data 29 ianuarie 2020 21:46:52
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int sol=-1,i,n,nr,s[100010],maxim,st,dr,x,poz1;
struct trie{
    int poz=0;
    trie *f[2];
    trie(){
      f[0]=f[1]=0;
    }
};
trie *root=new trie();
void add(trie *root,int bit, int val, int poz){
    if(bit==-1){
        root->poz=poz;
        return;
    }
    if(((val>>bit)&1)==0){
        if(!root->f[0])
            root->f[0]=new trie();
        add(root->f[0],bit-1,val,poz);
    }else{
         if(!root->f[1])
            root->f[1]=new trie();
        add(root->f[1],bit-1,val,poz);
    }
}
void query(trie *root,int bit,int val){
    if(bit==-1){
        poz1=root->poz;
        return;
    }
    if(root->f[1-((val>>bit)&1)])
        query(root->f[1-((val>>bit)&1)],bit-1,val);
    else
        query(root->f[((val>>bit)&1)],bit-1,val);

}
int main(){
    fin>>n>>s[1];
    for(i=2;i<=n;i++){
        fin>>x;
        maxim=max(x,maxim);
        s[i]=(s[i-1]^x);
    }
    while(maxim){
        nr++;
        maxim/=2;
    }
    add(root,nr,0,0);
    for(i=1;i<=n;i++){
        query(root,nr,s[i]);
        if((s[i]^s[poz1])>sol){
            sol=(s[i]^s[poz1]);
            st=poz1+1;
            dr=i;
        }
        add(root,nr,s[i],i);
    }
    fout<<sol<<" "<<st<<" "<<dr;
    return 0;
}