Cod sursa(job #661183)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 13 ianuarie 2012 22:36:33
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 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];

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 = ind = 0;
        memset( fiu, 0, sizeof(fiu) );
    }
};

Trie *T = new Trie();

void getBits(char* s, int n) {
    int i = 0, aux = 1<<20;
    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 max(int a, int b) { return a>b ? a : b; }

void insert(Trie *nod, char *s, int ind) {
    if( *s=='\n' ) {
        nod->cnt++;
        nod->ind = max( 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);
}

int que(Trie *nod, char *s) {
    if( *s=='\n' ) return nod->ind;

    int f = fChar(s);
    if( nod->fiu[f^1] ) que(nod->fiu[f^1], s+1);
    else 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);

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

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

        insert(T, s, i);
    }

    /*getBits(s, 2097151);
    printf("%s", s);*/

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

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