Cod sursa(job #2534360)

Utilizator radugnnGone Radu Mihnea radugnn Data 30 ianuarie 2020 14:58:07
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n,i,x,mx,biti,elem,sol=-1,st,dr;
int s[DIM];
struct nod{
    int poz;
    nod *f[2];
    nod(){
        poz=0;
        f[0]=0;
        f[1]=0;
    }
};
nod *rad=new nod;
void inserare(nod *p, int bit, int val, int poz){
    if(bit==-1){
        p->poz=poz;
        return;
    }
    int x=((val>>bit)&1);
    if(p->f[x]==NULL)
        p->f[x]=new nod;
    inserare(p->f[x],bit-1,val,poz);
}

int cautare(nod *p, int bit, int val){
    if (bit==-1)
        return p->poz;
    int x=((val>>bit)&1);
    if(p->f[1-x])
        cautare(p->f[1-x],bit-1,val);
    else
        cautare(p->f[x],bit-1,val);
}

int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>x;
        mx=max(mx,x);
        s[i]=(x^s[i-1]);
    }
    while(mx){
        biti++;
        mx/=2;
    }
    inserare(rad,biti,0,0);
    for(i=1;i<=n;i++){
        elem=cautare(rad,biti,s[i]);
        if((s[i]^s[elem])>sol){
            sol=(s[i]^s[elem]);
            st=elem+1;
            dr=i;
        }
        inserare(rad,biti,s[i],i);
    }
    fout<<sol<<" "<<st<<" "<<dr;

    return 0;
}