Cod sursa(job #1513294)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 29 octombrie 2015 12:02:12
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <cstdio>

const int NMAX = 100010;

char ans[22];
int vsum[NMAX];

char* converter (int x) {
    for (int i = 0; i <= 20; i++) {
        ans[i] = 0;
    }
    ans[21] = 2;

    for (int pos = 20; x; x >>= 1, pos--) {
        ans[pos] = x & 1;
    }

    char* p;
    p = ans;
    return ans;
}

struct Trie {
    int which, children;
    Trie *child[2];

    Trie () {
        which = 0;
        children = 0;
        child[0] = child[1] = NULL;
    }
};

Trie *T = new Trie;

void insertTrie (Trie *node, char *s, int pos) {
    if (*s == 2) {
        node->which = pos;
        return;
    }

    if (node->child[*s] == NULL) {
        node->child[*s] = new Trie;
        node->children++;
    }

    insertTrie (node->child[*s], s + 1, pos);
}

int searchTrie (Trie *node, char *s) {
    if (*s == 2 || !node->children) {
        return node->which;
    }

    if (*s == 0) {
        if (node->child[1]) {
            return searchTrie (node->child[1], s + 1);
        }
        else {
            return searchTrie (node->child[0], s + 1);
        }
    }
    else {
        if (node->child[0]) {
            return searchTrie (node->child[0], s + 1);
        }
        else {
            return searchTrie (node->child[1], s + 1);
        }
    }
}

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

    int sum = 0, ANS = -1, BEG, FIN, N;

    scanf ("%d", &N);
    for (int i = 1; i <= N; i++) {
        int X;
        scanf ("%d", &X);
        sum ^= X;
        vsum[i] = sum;

        int complem;
        complem = searchTrie (T, converter (sum));
        if ((sum ^ vsum[complem]) > ANS) {
            ANS = (sum ^ vsum[complem]);
            BEG = complem + 1;
            FIN = i;
        }
        insertTrie (T, converter (sum), i);
    }

    printf ("%d %d %d\n", ANS, BEG, FIN);

    return 0;
}