Cod sursa(job #308902)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 28 aprilie 2009 20:41:14
Problema Xor Max Scor 100
Compilator cpp Status done
Runda tot Marime 2.28 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;      
}