Cod sursa(job #1161535)

Utilizator SmarandaMaria Pandele Smaranda Data 31 martie 2014 11:58:00
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <cstdio>

using namespace std;

struct Trie {
    int  value;
    Trie *edges [2];

    Trie () {
        value = 0;
        edges [0] = NULL;
        edges [1] = NULL;
    }
};

const int N = 100001;
int n, a [N], XOR [N], index [N];
Trie *trie = new Trie;

void read () {
    int i;

    scanf ("%d", &n);
    for (i = 1; i <= n; i ++)
        scanf ("%d", &a [i]);
}

void insert (int x, int ind) {
    int i, b;
    Trie *node;
    node = trie;
    for (i = 21; i >= 0; i --) {
        if (x & (1 << i))
            b = 1;
        else b = 0;
        if (node -> edges [b] != NULL)
            node = node -> edges [b];
        else {
            node -> edges [b] = new Trie;
            node = node -> edges [b];
        }
    }
    if (node -> value < ind)
        node -> value = ind;
}

int query (int x) {
    int i, b;
    Trie *node;
    node = trie;
    for (i = 21; i >= 0; i --) {
        if (x & (1 << i))
            b = 0;
        else b = 1;
        if (node -> edges [b] != NULL)
            node = node -> edges [b];
        else
            if (node -> edges [!b] != NULL)
                node = node -> edges [!b];
            else break;
    }
    if (i >= 0)
        return 0;
    else return node -> value;
}

void solve () {
    int i, max = -1, st, dr, c;

    XOR [1] = a [1];
    index [1] = 0;
    insert (XOR [1], 1);
    for (i = 2; i <= n; i ++) {
        XOR [i] = XOR [i - 1] ^ a [i];
        index [i] = 0;
        index [i] = query (XOR [i]);
        insert (XOR [i], i);
    }

    for (i = 1; i <= n; i ++) {
        if (index [i] == 0)
            c = XOR [i];
        else c = XOR [i] ^ XOR [index [i]];
        if (c > max) {
            max = c;
            st = index [i] + 1;
            dr = i;
        }
        else
            if (c == max)
                if (dr > i) {
                    dr = i;
                    st = index [i] + 1;
                }
                else
                    if (dr == i && dr - st + 1 > i) {
                        st = index [i] + 1;
                        dr = i;
                    }
    }
    printf ("%d %d %d\n", max, st, dr);
}

int main () {
    freopen ("xormax.in", "r", stdin);
    freopen ("xormax.out", "w", stdout);

    read ();
    solve ();
    return 0;
}