Cod sursa(job #1306268)

Utilizator salam.bossSalam Valorosu salam.boss Data 30 decembrie 2014 19:35:42
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("xormax.in");
ofstream g ("xormax.out");

const int PMAX = 20;
const int NMAX = 100000 + 1;

struct Trie {
    int nr;
    Trie *fiu[2];
    Trie() {
        nr = 0;
        fiu[0] = fiu[1] = NULL;
    }
};

int n;
Trie *t;
int xor_sum[NMAX];

Trie *insereaza(int bit, int x, int i, Trie *t) {
    if (t == NULL) t = new Trie();
    if (bit == -1) {
        t->nr = i;
        return t;
    }
    int mask = x & (1 << bit);
    mask = (mask != 0);
    t->fiu[mask] = insereaza(bit - 1, x, i, t->fiu[mask]);
    return t;
}

int sol(int bit, int x, Trie *t) {
    if (t == NULL) return 0;
    if (bit == -1) return t->nr;
    int mask = x & (1 << bit);
    mask = (mask != 0);
    if (t->fiu[1 - mask] != NULL) return sol(bit - 1, x, t->fiu[1 - mask]);
    return sol(bit - 1, x, t->fiu[mask]);
}

void rezolva() {
    int j, rez = -1, a, b;
    f >> n;
    t = insereaza(PMAX, 0, 0, t);
    for (int i = 1; i <= n; i++) {
        f >> xor_sum[i];
        xor_sum[i] ^= xor_sum[i - 1];
        j = sol(PMAX, xor_sum[i], t);
        if ((xor_sum[i] ^ xor_sum[j]) > rez) {
            rez = xor_sum[i] ^ xor_sum[j];
            a = j + 1;
            b = i;
        }
        t = insereaza(PMAX, xor_sum[i], i, t);
    }
    g << rez << ' ' << a << ' ' << b << '\n';
}


int main() {
    rezolva();
    return 0;
}