Cod sursa(job #2026359)

Utilizator attack2002Girban Alexandru attack2002 Data 24 septembrie 2017 12:57:10
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<fstream>
using namespace std;
int v[100007] , sp[100007];
struct trie
{
    trie *z,*u;
    int urb;
    trie()
    {
        z=NULL;
        u=NULL;
        urb=0;
    }
}*rad;
trie *adaos(int X, int bit, trie *nod)
{
    if(nod == NULL)
    {
        nod = new trie;
    }
    if(bit == -1)
    {
        nod -> urb = X;
        return nod;
    }
    int fiu = sp[X] & (1<<bit);
    if(fiu == 0)
    {
        nod -> z = adaos(X,bit-1,nod -> z);
    }
    else
    {
        nod -> u = adaos(X,bit-1,nod -> u);
    }
    return nod;
}
int cauta(int val, int bit, trie *nod)
{
    if(bit==-1)
    {
        return nod -> urb;
    }
    int fiu = val & (1<<bit);
    if(fiu==0)
    {
        if(nod -> u != NULL)
        {
            return cauta(val, bit-1, nod->u);
        }
        else
        {
            return cauta(val, bit-1, nod->z);
        }
    }
    else
    {
        if(nod -> z != NULL)
        {
            return cauta(val, bit-1, nod->z);
        }
        else
        {
            return cauta(val, bit-1, nod->u);
        }
    }
}
int main()
{
    ifstream read("xormax.in");
    ofstream write("xormax.out");
    int n,cpdr(0),cpst(0);
    long long int maxxor=-1;
    read>>n;
    for(int i=1;i<=n;++i)
    {
        read>>v[i];
        sp[i] = sp[i-1] ^ v[i];
    }
    rad=adaos(0, 21, rad);
    for(int i=1;i<=n;++i)
    {
        int gasit=cauta(sp[i], 21, rad);
        if( (sp[gasit] ^ sp[i]) > maxxor)
        {
            maxxor = sp[gasit] ^ sp[i];
            cpdr = i;
            cpst = gasit + 1;
        }
        rad = adaos(i, 21, rad);
    }
    write << maxxor << " " << cpst << " " << cpdr ;
    return 0;
}