Cod sursa(job #1677065)

Utilizator serbanSlincu Serban serban Data 6 aprilie 2016 12:25:46
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>

using namespace std;

struct trie {
    trie *v[2] = {NULL, NULL};
    int r = 0;
} *t = new trie;

void bag(trie *p, int r, int lvl, int nr) {
    if(lvl == -1) {
        p->r = r;
        return ;
    }
    bool bit = nr & (1 << lvl);
    if(p->v[bit] == NULL)
        p->v[bit] = new trie;
    bag(p->v[bit], r, lvl - 1, nr);
}

int caut(trie *p, int lvl, int nr) {
    if(lvl == -1)
        return p->r;
    bool bit = (nr & (1 << lvl));
    if(!p->v[!bit])
        return caut(p->v[bit], lvl - 1, nr);
    return caut(p->v[!bit], lvl - 1, nr);
}

int x[100005], y, mx = -1, l, r;

int main()
{
    ifstream f("xormax.in");
    ofstream g("xormax.out");
    int n; f >> n;
    bag(t, 0, 21, 0);
    for(int i = 1; i <= n; i ++) {
        f >> y;
        x[i] = x[i - 1] ^ y;

        int poz = caut(t, 21, x[i]);
        int s = x[i] ^ x[poz];
        if(s > mx) {
            mx = s;
            l = poz + 1;
            r = i;
        }
        bag(t, i, 21, x[i]);
    }
    g << mx << " " << l << " " << r << "\n";
    return 0;
}