Cod sursa(job #1222763)

Utilizator cojocarugabiReality cojocarugabi Data 24 august 2014 12:29:33
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
# include <fstream>
# include <iostream>
# include <cstring>
using namespace std;
ifstream fi("xormax.in");
ofstream fo("xormax.out");
struct trie
{
    int x;
    trie *s[2];
    trie()
    {
        s[0]=s[1]=NULL;
        x=0;
    }
};
trie *t=new trie;
const int nmax=100005;
int S[nmax];
bool d[25];
int read()
{
    char c[30];
    fi>>c;
    int p=0,k=strlen(c);
    for (int i=0;i<k;++i) p=p*10+c[i]-'0';
    return (p);
}
int main(void)
{
    S[0]=0;
    int n=read(),Max=-1,p,u;
    trie *f=t;
    for (int i=1;i<22;++i) f->s[0]=new trie,f=f->s[0];
    f->x=0;
    for (int i=1;i<=n;++i)
    {
        S[i]=read()^S[i-1];
        for (int j=1;j<22;++j) d[j]=(S[i] & (1<<(21-j)));
        f=t;
        for (int j=1;j<22;++j)
            if (f->s[1-d[j]]) f=f->s[1-d[j]];else f=f->s[d[j]];
        int x=f->x;
        if (Max<S[i]^S[x]) Max=S[i]^S[x],u=i,p=x+1;
        f=t;
        for (int j=1;j<22;++j)
            if (f->s[d[j]]) f=f->s[d[j]];else f->s[d[j]]=new trie,f=f->s[d[j]];
        f->x=i;
    }
    fo<<Max<<" "<<p<<" "<<u<<"\n";
}