Cod sursa(job #1115657)

Utilizator smaraldaSmaranda Dinu smaralda Data 21 februarie 2014 22:22:06
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<cstring>
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

const int NMAX = 1e5;
int i, flag, p, len, pos[NMAX+5], xp[NMAX+5];
char s[25];

struct TRIE {
    set <int, greater <int> > pos;
    TRIE *edges[2];
    };

TRIE *init (TRIE *node) {
    if(node == NULL)
        node = new TRIE;

    node->edges[0] = node->edges[1] = NULL;
    return node;
}

void add (TRIE *node, int x) {
    int i;
    bool bit;

    for(i = 22; i >= 0; i--) {
        bit = x & (1 << i);

        if(node->edges[bit] == NULL) {
            node->edges[bit] = new TRIE;
            node->edges[bit] = init(node->edges[bit]);
        }

        node = node->edges[bit];
    }
    node->pos.insert(p);
}

int search (TRIE *node, int x) {
    int i;
    bool bit;

    for(i = 22; i >= 0; i--) {
        bit = !(x & (1 << i));

        node = node->edges[bit] == NULL ? node->edges[!bit] : node->edges[bit];
    }

    return *(node->pos.begin());
}
int main() {
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    char str[22];
    int n, x, val, valmax, st, dr;

    TRIE *start = NULL;
    start = init(start);

    scanf("%d",&n);

    p = 0;
    add(start, 0);
    for(i = 1; i <= n; i++) {
        scanf("%d",&x);
        xp[i] = xp[i - 1] ^ x;

        pos[i] = search(start, xp[i]);
        p = i;
        add(start, xp[i]);
    }


    valmax = -1;
    for(i = 1; i <= n; i++) {
        val = xp[i] ^ xp[pos[i]];
        if(val > valmax) {
            valmax = val;
            st = pos[i] + 1;
            dr = i;
            }
        }

    printf("%d %d %d\n",valmax,st,dr);
    return 0;
}