Cod sursa(job #2669085)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 6 noiembrie 2020 01:05:59
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
struct trie
{
    trie *fiu[2];
    trie()
    {
        memset(fiu, 0, sizeof(fiu));
    }
};
trie *T = new trie;
void mask(int x, char *s1, char *s2)
{
    int i;
    for(i = N ; i >= 0 ; i --)
        if(x & (1 << i))
            s1[N - i] = '1', s2[N - i] = '0';
        else
            s1[N - i] = '0', s2[N - i] = '1';
    s1[N + 1] = s2[N + 1] = '\n';
}
void addMask(trie *nod, char *s)
{
    if(*s == '\n')
        return;
    if(nod->fiu[*s - '0'] == 0)
        nod->fiu[*s  - '0'] = new trie;
    addMask(nod->fiu[*s - '0'], s + 1);
}
int findMask(trie *nod, char *s, int k)
{
    if(*s == '\n')
        return 0;
    int pos = *s - '0';
    if(nod->fiu[pos] == 0)
        pos = (1 ^ pos);
    return (pos << k) | findMask(nod->fiu[pos], s + 1, k - 1);
}
int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    int n, i, t, x, xormax, y;
    char s1[22], s2[22];
    scanf("%d", &n);
    xormax = t = 0;
    mask(t, s1, s2);
    addMask(T, s1);
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%d", &x);
        t ^= x;
        mask(t, s1, s2);
        addMask(T, s1);
        y = findMask(T, s2, 20);
        xormax = max(xormax, t ^ y);
    }
    printf("%d\n", xormax);
    return 0;
}