Cod sursa(job #148489)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 4 martie 2008 13:39:07
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <stdio.h>  
  
struct trie  
{  
    trie() : s(NULL), d(NULL), x(0){}  
    int x;  
    trie *s, *d;  
};  
  
int p = -1, n, a1, b1, v[100005];  
trie *t;  
  
void citire()  
{  
    freopen("xormax.in", "r", stdin);  
    freopen("xormax.out", "w", stdout);  
    
	int i;
    scanf("%d", &n);  
    for (i = 1; i <= n; ++i)  scanf("%d", &v[i]);  
}  
  
void constr(int k, int pas)  
{  
    trie *c = t;  
    int i;  
      
    for (i = 20; i >= 0; --i)  
        if ((k >> i) & 1)  
            c = c->d == NULL ? c->d = new trie : c->d;  
        else  
            c = c->s == NULL ? c->s = new trie : c->s;  
    c->x = pas;  
}  
  
void eval(int k, int &rez, int &poz)  
{  
    trie *c = t;  
    int i;  
      
    rez = 0;  
    for (i = 20; i >= 0; --i)  
        if ((k >> i) & 1)  
        {  
            if (c->s != NULL)  
            {  
                c = c->s;  
                rez |= 1 << i;  
            }  
            else c = c->d;  
        }  
        else  
        {  
            if (c->d != NULL)  
            {  
                c = c->d;  
                rez |= 1 << i;  
            }  
            else c = c->s;  
        }  
    poz = c->x;  
}  
  
void calcul()  
{  
    int i, val = 0, aux, poz;  
      
    t = new trie;  
    constr(0, 0);  
      
    for (i = 1; i <= n; ++i)  
    {  
        val ^= v[i];  
        eval(val, aux, poz);  
        if (aux > p)  
        {  
            p = aux;  
            a1 = poz;  
            b1 = i;  
        }  
        constr(val, i);  
    }  
    printf("%d %d %d\n", p, a1+1, b1);  
}  
  
int main()  
{  
    citire();  
    calcul();  
    return 0;  
}