Cod sursa(job #911411)

Utilizator razvan.popaPopa Razvan razvan.popa Data 11 martie 2013 16:57:13
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<cstdio>
#define infile "xormax.in"
#define outfile "xormax.out"
#define nMax 100005
#define INF (1 << 30)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
using namespace std;

struct Trie{
    int idx;
    Trie *nxt[2];

    Trie(){
        idx = 0;
        nxt[0] = nxt[1] = NULL;
    }
} *T;

int S[nMax];

int N, Best, Left, Right;


void insert(Trie *R, int index, int bit){
    if(bit == -1){
        R -> idx = index;
        return;
    }

    bool el = (S[index] & (1<<bit));
    if(!R -> nxt[el])
       R -> nxt[el] = new Trie();

    insert(R -> nxt[el], index, bit - 1);
}

int find(Trie *R, int index, int bit){
    if(bit < 0)
        return R -> idx;

    bool el = !(S[index] & (1<<bit));

    if(R -> nxt[el])
       return find(R -> nxt[el], index, bit - 1);

    else if(R -> nxt[1 - el])
       return find(R -> nxt[1 - el], index, bit - 1);

    return R -> idx;
}


int main(){
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    scanf("%d", &N);

    T = new Trie();

    FOR(i,1,N){
        scanf("%d", &S[i]);

        S[i] ^= S[i-1];

        insert(T, i, 21);

        int idx = find(T, i, 21);

        if((S[i] ^ S[idx]) > Best){
            Best = S[i] ^ S[idx];
            Left = idx + 1;
            Right = i;
        }
    }

    printf("%d %d %d\n", Best, Left, Right);

    fclose(stdin);
    fclose(stdout);

    return 0;
}