Cod sursa(job #1608701)

Utilizator hasmasandragosHasmasan Dragos hasmasandragos Data 22 februarie 2016 12:02:08
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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=-1,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)
            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));

        aux=query(root,mask,20);
        if ((dp[aux]^dp[i])>summax)
        {
            bg=aux+1;
            en=i;
            summax=(dp[aux]^dp[i]);
        }
        add_element(root,mask,20,i);
    }

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

    return 0;
}