Cod sursa(job #1600678)

Utilizator hasmasandragosHasmasan Dragos hasmasandragos Data 15 februarie 2016 12:15:55
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
const int nmax=100005;
int n,dp[nmax],x,i,summax,bg,en,j;
bool mask[25];

struct trie
{
    int bst;
    trie *fiu[2];
    trie ()
    {
        bst=-1;
        fiu[0]=fiu[1]=NULL;
    }
};

trie *root = new trie();

void add_element (trie *nod, bool m[] , int siz , int ind)
{
    if (siz<0)
    {
        if (ind>nod->bst) /// pentru determinarea secventei de lungime minima
         nod->bst=ind;
        return ;
    }

    if (nod->fiu[m[siz]]==NULL)
        nod->fiu[m[siz]]=new trie();

    add_element(nod->fiu[m[siz]],m,siz-1,ind);
}

int query (trie *nod, bool m[] , int siz)
{
    if (siz<0)
        return nod->bst;
    if (nod->fiu[!m[siz]])
        return query(nod->fiu[!m[siz]],m,siz-1);
    else if (nod->fiu[m[siz]])
        return query(nod->fiu[m[siz]],m,siz-1);
    return -1;
}

int main()
{
    int aux;
    f>>n;
    add_element(root,mask,20,0);
    for (i=1;i<=n;i++)
    {
        f>>x;
        dp[i]=(x^dp[i-1]);
        for (j=0;j<=20;j++)
            mask[j]=(dp[i]&(1<<j));

        add_element(root,mask,20,i);

        if ((dp[aux]^dp[i])>summax)
        {
            summax=(dp[aux]^dp[i]);
            bg=aux+1;
            en=i;
        }

        add_element(root,mask,20,i);
    }

    g<<summax<<" "<<bg<<" "<<en;

    return 0;
}