Cod sursa(job #2888155)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 10 aprilie 2022 18:52:56
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
//Ilie Dmitru
#include<fstream>
#include<cstdio>
typedef long long int ll;
const int NMAX=500005;
const ll MOD=194767;
const int maxBIT=1<<21;

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

struct trie
{
    trie* next[2];
    bool exists;
};

void init(trie*& t)
{
    t=new trie;
    t->exists=0;
    t->next[0]=t->next[1]=0;
}

void push(trie*& t, int x, int bit=maxBIT)
{
    int val=!!(x&bit);
    if(!t)
        init(t);
    if(!bit)
        t->exists=1;
    else
        push(t->next[val], x, bit>>1);
}

trie* t;

char s[21];
void print(trie* t, int dpth=0)
{
    if(t->exists)
        printf("%s\n", s);
    if(t->next[0])
    {
        s[dpth]='0';
        print(t->next[0], dpth+1);
    }
    if(t->next[1])
    {
        s[dpth]='1';
        print(t->next[1], dpth+1);
    }
}

void clear(trie*& t)
{
    if(t)
    {
        clear(t->next[0]);
        clear(t->next[1]);
        delete t;
    }
}

int findMax(trie* t, int x, int bit=maxBIT)
{
    int val=!(x&bit), res=0;
    if(!t)
        return 0;
    if(t->next[val])
        res=bit|findMax(t->next[val], x, bit>>1);
    else
        res=findMax(t->next[!val], x, bit>>1);
    return res;
}

int main()
{
    int i, N, a, x=0, r, ans=0;
    f>>N;
    push(t, 0);
    for(i=0;i<N;++i)
    {
        f>>a;
        x^=a;
        r=findMax(t, x);
        if(r>ans)
            ans=r;
        push(t, x);
    }
    g<<ans;
    clear(t);
    f.close();
    g.close();
    return 0;
}