Cod sursa(job #1204503)

Utilizator tudorv96Tudor Varan tudorv96 Data 3 iulie 2014 01:16:44
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
using namespace std;

ifstream fin ("xormax.in");
ofstream fout ("xormax.out");

const int N = 1e5 + 5, SZ = (1 << 23) + 5;

int xp[N], xpmax, n, sol, trie[SZ], bg = 0, en = 0;

void insert (int i, int poz, int node) {
    trie[node] = i;
    int next = node * 2 + ((xp[i] & (1 << poz)) ? 1 : 0);
    if (poz >= 0)
        insert (i, poz - 1, next);
}

int find (int x, int poz, int node) {
    if (poz < 0)
        return trie[node];
    int next = (x & (1 << poz)) ? 0 : 1;
    if (trie[node * 2 + next] == -1)
        next = !next;
    return find(x, poz - 1, node * 2 + next);

}

int main() {
    for (int i = 1; i < SZ; ++i)
        trie[i] = -1;
    fin >> n;
    for (int x, i = 1; i <= n; ++i) {
        fin >> x;
        xp[i] = xp[i-1] ^ x;
        xpmax = max(xpmax, xp[i]);
    }
    int b = 0;
    while (xpmax) {
        b++;
        xpmax >>= 1;
    }
    insert (0, b - 1, 1);
    for (int i = 1; i <= n; ++i) {
        int now = find(xp[i], b - 1, 1);
        if ((xp[i] ^ xp[now]) > sol) {
            bg = now + 1;
            en = i;
            sol = xp[i] ^ xp[now];
        }
        insert (i, b - 1, 1);
    }
    fout << sol << " " << bg << " " << en;
}