Cod sursa(job #2102371)

Utilizator smashsmash everything smash Data 8 ianuarie 2018 18:46:03
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<fstream>

using namespace std;
ifstream cin ("xormax.in");
ofstream cout ("xormax.out");
int maxim,b[25],t,f,l;
struct trie
{   int nr;
    trie *fiu[2];
    trie()
    {
        fiu[0]=fiu[1]=NULL;
    }
} *rad=new trie;
int n,k,p,cnt=-1;
void see (trie *nod)
{   cnt--;
    t=nod->nr;
    if(cnt<0) return;
    if(nod->fiu[b[cnt]]!=NULL)
        k=k+(1<<cnt);
        if(nod->fiu[b[cnt]]!=NULL) see(nod->fiu[b[cnt]]);
        else if(nod->fiu[b[cnt]^1]!=NULL) see(nod->fiu[b[cnt]^1]);
        else {t=nod->nr; return;}
}
void add (trie *nod)
{
    cnt--;
    if(cnt<0) {nod->nr=t; return;}
    if(nod->fiu[b[cnt]]==NULL) nod->fiu[b[cnt]]=new trie;
    add(nod->fiu[b[cnt]]);
}
void solve ()
{ int x,sol;
    cin>>n>>sol; maxim=sol;
    t=0; cnt=22;
    add(rad);
    p=sol; cnt=-1;
        while(p) b[++cnt]=(p%2),p/=2;
        while(cnt<21) b[++cnt]=0; cnt++; t=1;
        add(rad);
    for(int i=2;i<=n;i++)
    {
        cin>>x; sol=sol ^ x; p=sol; cnt=-1;
        while(p) b[++cnt]=(p%2)^1,p/=2;
        while(cnt<21) b[++cnt]=1; cnt++;
        k=0;
        see(rad);
        if(k>maxim) maxim=k,l=i,f=t;
        p=sol; cnt=-1;
        while(p) b[++cnt]=(p%2),p/=2;
        while(cnt<21) b[++cnt]=0; ++cnt; t=i;
        add(rad);
    }
    cout<<maxim<<" "<<f+1<<" "<<l<<"\n";
}
int main()
{
    solve();
    cin.close();
    cout.close();
    return 0;
}