Cod sursa(job #2303206)

Utilizator racheriunicolaechowchow racheriunicolae Data 15 decembrie 2018 20:22:40
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;
const int INTSIZE = 30;
struct trie
{
    int val;
    trie *nxt[2];
    trie()
    {
        val = 0;
        nxt[0] = nxt[1] = 0;
    }
};
void add(trie *p , int pre)
{
    int i;
    for(i = INTSIZE ; i >=0 ; i--)
    {
        bool res = (1 << i) & pre;

        if(p -> nxt[res] == NULL)
            p -> nxt[res] = new trie();

        p = p -> nxt[res];
    }
    p -> val = pre;
}
int query(trie *p , int pre)
{
    int i;
    for(i = INTSIZE ; i >= 0; i--)
    {
        bool res = pre & (1 << i);

        if(p -> nxt[1 - res] != NULL)
            p = p -> nxt[1 - res];

        else if(p -> nxt[res] != NULL)
            p = p -> nxt[res];
    }
    return (pre ^ (p -> val));
}
const int NMAX = 1e5 + 5;
int n , i , v[NMAX] , pre, ans;
int main()
{
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    trie *p = new trie();
    add(p , 0);
    fin >> n;
    for(i = 1; i <= n; i++)
    {
        fin >> v[i];
        pre = pre ^ v[i];
        add(p , pre);
        ans = max(ans , query(p , pre));
    }
    fout << ans;
    return 0;
}
///