Cod sursa(job #877277)

Utilizator ericptsStavarache Petru Eric ericpts Data 12 februarie 2013 18:48:57
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <cstdio>

using namespace std;


int best = -1000;

struct trie
{
    int where;
    trie * next[2];
    trie()
    {
        next[0]=next[1]=0;
    }
};

trie * T = new trie;
int now;
int n;
int go,fin;
int v[100005];

const inline int max(const int &a,const int &b)
{
    return a >= b ? a : b;
}

void query(trie * nod,int bit)
{
    while(bit != -1)
    {
        if((1<<bit) & v[now])
        {
            if(nod->next[0])
                nod = nod->next[0];
            else
                nod = nod->next[1];
        }
        else
        {
            if(nod->next[1])
                nod = nod->next[1];
            else
                nod = nod->next[0];
        }
        --bit;
    }
    bit = v[nod->where] xor v[now];
    if(bit > best)
    {
        best = bit;
        go = nod->where + 1;
        fin = now;
    }
}


void update(trie * nod,int bit)
{
    while(bit != -1)
    {
        if((1<<bit) & v[now])
        {
            if(!nod->next[1])
                nod->next[1]=new trie;
            nod = nod->next[1];
        }
        else
        {
            if(!nod->next[0])
                nod->next[0]=new trie;
            nod = nod->next[0];
        }
        --bit;
    }
    nod->where = now;
}


int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int i;

    scanf("%d\n",&n);

    update(T,20);
    for(i=1;i<=n;++i)
    {
        now = i;
        scanf("%d",v+i);
        v[i] ^= v[i-1];
        query(T,20);
        update(T,20);
    }

    printf("%d\n%d %d\n",best,go,fin);

    return 0;
}