Cod sursa(job #2155940)

Utilizator mateibanuBanu Matei Costin mateibanu Data 8 martie 2018 12:06:27
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <bits/stdc++.h>

using namespace std;

#define ll long long

struct trie{
    int poz;
    trie *z,*u;

    trie(){
        poz=0;
        z=0;
        u=0;
    }
};

int v[100010],mx,start,stop,r;
trie *o = new trie;

void add(int x,int p){
    trie *nod=o;
    for (int i=1<<21;i>0;i>>=1){
        if (x&i){
            if (nod->u==NULL)
                nod->u = new trie;
            nod=nod->u;
        }
        else {
            if (nod->z==NULL)
                nod->z = new trie;
            nod=nod->z;
        }
    }
    nod->poz=p;
}

int check(int x){
    trie *nod=o;
    int t=0;
    for (int i=1<<21;i>0;i>>=1){
        if ((!(x&i))&&nod->u){
            nod=nod->u;
            t+=i;
        }
        else if ((x&i)&&nod->z){
            nod=nod->z;
            t+=i;
        }
        else if (nod->u) nod=nod->u;
        else if (nod->z) nod=nod->z;
        else break;
    }
    r=1+nod->poz;
    return t;
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n,aux;
    scanf("%d %d",&n,&v[1]);
    mx=v[1];start=1;stop=1;
    for (int i=2;i<=n;i++){
        scanf("%d",&v[i]);
        if (mx<v[i]){
            mx=v[i];
            start=i;
            stop=i;
        }
        v[i]=v[i-1]^v[i];
        if (mx<v[i]){
            mx=v[i];
            start=1;
            stop=i;
        }
    }
    add(v[1],1);
    add(v[2],2);
    for (int i=3;i<=n;i++){
        aux=check(v[i]);
        if (aux>mx||(aux==mx&&i>stop)||(aux==mx&&i==stop&&start<r)){
            mx=aux;
            start=r;
            stop=i;
        }
        add(v[i],i);
    }
    printf("%d %d %d",mx,start,stop);
    return 0;
}