Cod sursa(job #315873)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 17 mai 2009 16:20:16
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <stdio.h>   
  
#define NMAX 100001   
  
struct Nod   
{   
    int inf;   
    int ind;   
    Nod* urm[2];      
};   
  
typedef Nod* PNod;   
  
int N;   
int nr, x[NMAX];   
int max, put_max, start, stop;   
PNod R;   
  
using namespace std;   
  
// creez arbore binar cu put_max noduri cu val bitului 0 (numai fii stanga)   
void init()   
{   
    PNod p,nou;   
    p = new Nod;   
    p->ind = 0;   
    p->urm[0] = NULL;   
    p->urm[1] = NULL;   
    R = p;   
    for (int i = 0; i<put_max; ++i)   
    {   
        nou = new Nod;   
        nou->ind = 0;   
        nou->urm[0] = NULL;   
        nou->urm[1] = NULL;   
        p->urm[0] = nou;      
        p = nou;   
    }   
}   
  
// caut in arbore un drum egal cu complementul lui x, adica un xor cat mai mare   
void query(int x, int ind)   
{   
    PNod p = R;    
    int mask = 1 << (put_max-1);   
    int bit, res = 0, st = 0;   
    for (int i = put_max-1; i>=0; --i)   
    {   
        st = p->ind;   
        bit = (x&mask)>>i;   
        bit ^= 1;   
        if (p->urm[bit])   
            res+=mask;   
        else   
            bit ^= 1;   
        p = p->urm[bit];   
        mask >>=1;   
    }   
    if (res>max)   
    {   
        max = res;   
        start = st+1;   
        stop = ind;   
    }   
}   
  
// bag in arbore drumu lui x ca sa pot xora mai tarziu cu altii   
void update(int x, int ind)   
{   
    PNod p = R;   
    int mask = 1 << (put_max-1);   
    int bit;   
    for (int i = put_max-1; i>=0; --i)   
    {   
        p->ind = ind;   
        bit = (x&mask)>>i;   
        if (!(p->urm[bit]))   
        {   
            PNod nou = new Nod;   
            nou->ind = ind;   
            nou->urm[0] = NULL;   
            nou->urm[1] = NULL;   
            p->urm[bit] = nou;   
        }   
        p = p->urm[bit];   
        mask >>= 1;   
    }   
}   
  
int main()   
{   
    freopen("xormax.in", "r", stdin);   
    freopen("xormax.out", "w", stdout);   
           
    scanf("%d", &N);   
    scanf("%d", &x[0]);   
       
    max = -1;   
    put_max = 0;   
       
    for (int i = 1; i<N; ++i)   
    {   
        scanf("%d", &nr);   
        x[i] = x[i-1]^nr;   
        while (nr>=1 << put_max)   
            ++put_max;   
    }   
  
    init();   
  
    for (int i = 0; i<N; ++i)   
    {           
        query(x[i], i+1);   
        update(x[i], i+1);   
    }   
       
    printf("%d %d %d", max, start, stop);   
       
    return 0;      
}