Cod sursa(job #760)

Utilizator StTwisterKerekes Felix StTwister Data 11 decembrie 2006 20:19:22
Problema Xor Max Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 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;   
}