Cod sursa(job #292379)

Utilizator lexu93Todor Alex lexu93 Data 31 martie 2009 08:43:42
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <algorithm>   
#include <stdio.h>   
  
using namespace std;   
  
class NodTrie   
{   
    public:   
        int poz, nrFii;   
        NodTrie *fii[2];   
  
        NodTrie()   
        {   
            memset(fii, 0, sizeof(fii));   
            poz = nrFii = 0;   
        }   
};   
  
NodTrie *radTrie = new NodTrie;   
int n, sumXor, start = 1, finish = 1, maxGs, locGs;   
  
void addTrie(NodTrie *nod, int level, int key, int place)   
{   
    if (!level)   
    {   
        nod->poz = place;   
        return;   
    }   
  
    level--;   
    if (!nod->fii[(key & (1 << level)) >> level])   
    {   
        nod->nrFii++;   
        nod->fii[(key & (1 << level)) >> level] = new NodTrie;   
    }   
  
    addTrie(nod->fii[(key & (1 << level)) >> level], level, key, place);   
}   
  
int cautaOpus(NodTrie *nod, int level, int key)   
{   
    if (!level)   
    {   
        locGs = nod->poz;   
           
        return 0;   
    }   
  
    level--;   
    if (nod->fii[1 ^ ((key & (1 << level)) >> level)])   
        return ((1 ^ ((key & (1 << level)) >> level)) << level) + cautaOpus(nod->fii[1 ^ ((key & (1 << level)) >> level)], level, key);   
    else return (key & (1 << level)) + cautaOpus(nod->fii[(key & (1 << level)) >> level], level, key);   
}   
  
int main()   
{   
    freopen("xormax.in", "r", stdin);   
    freopen("xormax.out", "w", stdout);   
  
    scanf("%d", &n);   
  
    addTrie(radTrie, 24, 0, 0);   
    for (int i = 1; i <= n; i++)   
    {   
        int elem;   
        scanf("%d", &elem);   
  
        sumXor ^= elem;   
        int valMax = cautaOpus(radTrie, 24, sumXor);   
        if (maxGs < (sumXor ^ valMax))   
        {   
            maxGs = (sumXor ^ valMax);   
            start = locGs + 1;   
            finish = i;   
        }   
  
        addTrie(radTrie, 24, sumXor, i);   
    }   
  
    printf("%d %d %d\n", maxGs, start, finish);   
  
    fclose(stdin);   
    fclose(stdout);   
    return 0;   
}