Cod sursa(job #1537787)

Utilizator algebristulFilip Berila algebristul Data 28 noiembrie 2015 00:03:50
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>

#define FILEIN "xormax.in"
#define FILEOUT "xormax.out"

using namespace std;

int a[100005];

struct trie {
    int pos;
    struct trie * next[2];
    trie() {
        pos = -1;
        next[0] = next[1] = NULL;
    }

    void update(int mask, int bpos, int val) {
        if (bpos == -1) {
            pos  = val;
            return;
        }

        int bit = mask & (1 << bpos);
        bit = (bit > 0) ? 1 : 0;

        if (next[bit] == NULL)
            next[bit] = new trie;

        next[bit]->update(mask, bpos - 1, val);
    }

    int query(int mask, int bpos) {
        if (bpos == -1) {
            return pos;
        }

        int bit = mask & (1 << bpos);
        bit = (bit > 0) ? 0 : 1;
        if (next[bit]) {
            return next[bit]->query(mask, bpos - 1);
        } else {
            return next[bit ^ 1]->query(mask, bpos - 1);
        }
    }

    ~trie() {
        delete next[0];
        delete next[1];
    }
} * T;

int main() {
    T = new trie;
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    int n, sum = 0, x;
    int sol = -1, start, stop;

    cin >> n;

    T->update(0, 20, 0);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] ^= a[i-1];

        int l = T->query(a[i], 20);
        if (a[l] ^ a[i] > sol) {
            sol = a[l] ^ a[i];
            start = l + 1;
            stop = i;
        }

        T->update(a[i], 20, i);
    }

    cout << sol << ' ' << start << ' ' << stop << '\n';

    delete T;

    return 0;
}