Cod sursa(job #3165505)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 6 noiembrie 2023 12:43:44
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<cstdio>
#define N 100000
#define lg 20
using namespace std;

struct Nod{
    Nod *fii[2];
    int poz;
    Nod(){
        poz=0;
        fii[0]=NULL;
        fii[1]=NULL;
    }
};

Nod *r;
int pozS;
int s[22];
int v[N+1];


Nod *adauga(Nod *p,int l){
    if (p==NULL) p=new Nod;
    if (l==-1){
        if (p-> poz==0 ||p-> poz<pozS) p-> poz=pozS;
        return p;
    }
    p-> fii[s[l]]=adauga(p-> fii[s[l]],l-1);
    return p;
}

int query(Nod *p,int l){
    if (l==-1) return p-> poz;

    if (p-> fii[s[l]^1]!=NULL) return query(p-> fii[s[l]^1],l-1);
    else return query(p-> fii[s[l]],l-1);
}


int main(){
    freopen ("xormax.in","r",stdin);
    freopen ("xormax.out","w",stdout);
    int n,i,max,st,fn,j;
    int aux;

    scanf ("%d",&n);

    for(i=1;i<=n;i++){
        scanf ("%d",&v[i]);
        v[i]^=v[i-1];
    }

    r=adauga(r,lg);

    max=v[1];
    st=1;
    fn=1;
    for(i=1;i<=n;i++){
        for(j=0;j<=lg;j++)
            s[j]=((1<<j)&v[i])>>j;

        aux=query(r,lg);

        if ((v[aux]^v[i])>max){
            max=(v[aux]^v[i]);
            st=aux+1;
            fn=i;
        }

        pozS=i;
        adauga(r,lg);
    }

    printf ("%d %d %d",max,st,fn);
    return 0;
}