Cod sursa(job #1783943)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 19 octombrie 2016 17:01:22
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>

using namespace std;

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

int n, i, j, r, x;
int maxim, lmax, rmax;
int a[100005];

struct trie {
    int poz;
    trie* lg[2];
    trie() {
        lg[0] = lg[1] = 0;
        poz = 0;
    }
};

void add(trie *t, int x, int p) {
    int k;
    trie *k1 = t;
    while (p > 0) {
        if ((1 << (p-1)) & x)
            k = 1;
        else k = 0;
        if (k1 -> lg[k] == 0)
            k1 -> lg[k] = new trie();
        k1 = k1 -> lg[k];
        p--;
    }
    k1 -> poz = i;
}

int Find(trie *t, int x, int p) {
    int k;
    trie *k1 = t;
    while (p > 0) {
        if ((1 << (p-1)) & x)
            k = 0;
        else k = 1;
        if (k1 -> lg[k] == 0)
            k = 1 - k;
        k1 = k1 -> lg[k];
        p--;
    }
    return k1 -> poz;
}

int main() {
    trie* t = new trie();
    maxim = -1;
    f >> n;
    add(t, 0, 20);
    for (i = 1; i <= n; i++) {
        f >> x;
        a[i] = (a[i-1] ^ x);
        add(t, a[i], 20);
        j = Find(t, a[i], 20);
        r = (a[j] ^ a[i]);
        if (r > maxim)
            maxim = r, rmax = i, lmax = j+1;
    }
    g << maxim << ' ' << lmax << ' ' << rmax;
    return 0;
}