Cod sursa(job #765658)

Utilizator test666013Testez test666013 Data 8 iulie 2012 18:59:16
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 100001
#define ln printf("\n")

int a[MAX],sum[MAX],n;

struct trie{
    struct trie *f[2];
    int idx; }*t;

void adauga(int x,int idx){
    trie *g = t;
    int urm;
    for(int i=20;i>=0;i--)
    {
        if(x & (1<<i))urm = 1; else urm = 0;
        if(g->f[urm] == 0)g->f[urm] = new trie;
        g = g->f[urm];
    }
        g->idx = idx; // setam pozitia in care am gasit suma respectiva
}

int search(int x){
    trie *g = t;
    int urm;
    for(int i=20;i>=0;i--)
    {
        if(x & (1<<i))urm = 0; else urm = 1; // opusul bitului
        if(g->f[urm]) g = g->f[urm]; else g = g->f[(!urm)];
    }
    return g->idx;
}

void rezolva(){

    t = new trie;
    int best = a[1], l_idx = 1 ,r_idx = 1, p;
    for(int i=1;i<=n;i++)
    {
        sum[i] = sum[i-1] ^ a[i];
        adauga(sum[i],i); // adaugam suma respectiva in trie cu pozitia i
        p = search(sum[i]); // cautam valoarea optima
        if( (sum[i] ^ sum[p]) > best )
        {
            best = sum[i] ^ sum[p];
            l_idx = p + 1;
            r_idx = i;
        }
    }
        printf("%d %d %d\n",best,l_idx,r_idx);
}

/*
void rezolva(){
    for(int i=1;i<=n;i++)sum[i] = sum[i-1] ^ a[i];

    int best = -1, l_idx, r_idx, x;
    for(int i=1;i<=n;i++)
    {

        for(int j=i;j>0;j--)
        {
            x = sum[j-1] ^ sum[i];
            if(x > best)
            {
                best = x;
                l_idx = j;
                r_idx = i;
            }
        }
    }
    printf("%d %d %d\n",best,l_idx,r_idx);
}*/

int main(){
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    rezolva();
    return 0;
}