Cod sursa(job #661779)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 15 ianuarie 2012 11:10:54
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include<stdio.h>
#include<string.h>
#define inf "xormax.in"
#define outf "xormax.out"
#define NMax 100001
#define INF 0x3f3f3f3f
using namespace std;

int N, A[NMax], S[NMax];
const int bits = 22;

void read()
{
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d", &A[i]);
}

struct Trie {
    int ind;
    Trie* fiu[2];

    Trie() {
        ind = 0;
        memset( fiu, 0, sizeof(fiu) );
    }
};

Trie *T = new Trie();

void insert(Trie *nod, int x, int ind) {
    for(int i=bits; i>=0; i--) {
        int bit = (x & (1<<i));
        if( bit ) {
            if( nod->fiu[1]==0 ) nod->fiu[1] = new Trie();
            nod = nod->fiu[1];
            continue;
        }
        if( nod->fiu[0]==0 ) nod->fiu[0] = new Trie();
        nod = nod->fiu[0];
    }
    nod->ind = ind;
}

int que(Trie *nod, int x) {
    for(int i=bits; i>=0; i--) {
        int bit = (x & (1<<i));
        if( bit ) {
            if( nod->fiu[0] ) nod = nod->fiu[0];
            else nod = nod->fiu[1];
        }
        else {
            if( nod->fiu[1] ) nod = nod->fiu[1];
            else nod = nod->fiu[0];
        }
    }
    return nod->ind;
}

void solve()
{
    S[1] = A[1];
    for(int i=2; i<=N; i++) S[i] = A[i]^S[i-1];

    insert(T, 0, 0);

    int sol = -INF, start, stop;
    for(int i=1; i<=N; i++) {
        int p = que(T, S[i]);

        if( sol < S[i]^S[p] ) sol = S[i]^S[p], start = p+1, stop = i;

        insert(T, S[i], i);
    }

    printf("%d %d %d", sol, start, stop);
}

int main()
{
	freopen(inf,"r",stdin); freopen(outf,"w",stdout);
	read(); solve();
	return 0;
}