Cod sursa(job #661155)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 13 ianuarie 2012 21:43:20
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 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];
int rez, j;

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

struct Trie {
    int cnt, nrfii, ind;
    Trie* fiu[2];

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

Trie *T = new Trie();

void getBits(char* s, int n) {
    int i = 0, aux = 1<<21;
    while( aux ) {
        if( aux & n ) s[i++] = '1';
        else s[i++] = '0';
        aux >>= 1;
    }
    s[i++] = '\n'; s[i] = '\0';
}

inline int fChar(char *s) { return *s-'0'; }

inline int min(int a, int b) { return a<b ? a : b; }

void insert(Trie *nod, char *s, int ind) {
    if( *s=='\n' ) {
        nod->cnt++;
        nod->ind = min( nod->ind, ind );
        return;
    }

    int f = fChar(s);
    if( nod->fiu[f]==0 ) {
        nod->fiu[f] = new Trie();
        nod->nrfii++;
    }

    insert(nod->fiu[f], s+1, ind);
}

void que(Trie *nod, char *s) {
    if( *s=='\n' ) {
        rez >>= 1;
        j = nod->ind;
        return;
    }

    int f = fChar(s);
    if( nod->fiu[f^1] ) {
        rez |= (f^1); rez <<= 1;
        que(nod->fiu[f^1], s+1);
    }
    else {
        rez |= f; rez <<= 1;
        que(nod->fiu[f], s+1);
    }
}

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

    int sol = S[1], start = 1, stop = 1;

    char *s = new char[30]; getBits(s, S[1]);
    insert(T, s, 1);

    //printf("%d\n", que(T, s) );

    for(int i=2; i<=N; i++) {
        getBits(s, S[i]);
        rez = 0; que(T, s);

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

        insert(T, s, i);
    }

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

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