Cod sursa(job #978788)

Utilizator Kira96Denis Mita Kira96 Data 29 iulie 2013 18:14:06
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<fstream>
#include<cstring>
#define c *p
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int A,x,st,dr,poz,pot,cur,j,S,a,t,n,best,i;
char s[30];
struct Trie
{
    int po;
    Trie *fiu[2];
    Trie()
    {
        po=0;
        memset(fiu,0,sizeof(fiu));
    }
};
Trie *r=new Trie;
int find(Trie *nod,char *p)
{
    if(c=='a')
    {
        if(nod->po)
        return 1;
        return 0;
    }
    if(nod->fiu[c]!=NULL)
        return find(nod->fiu[c],p+1);
    return 0;
}
void insert(Trie *nod,char *p)
{
    if(c=='a')
    {
        nod->po=i;
        return ;
    }
    if(nod->fiu[c]==NULL)
    {
        nod->fiu[c]=new Trie;
    }
    insert(nod->fiu[c],p+1);
}
void solut(Trie *nod,char *p)
{
    pot>>=1;
    if(c=='a')
    {
        poz=nod->po;
        return ;
    }
    if(nod->fiu[!c]!=NULL)
    {
        A|=pot*(!c);
        solut(nod->fiu[!c],p+1);
    }
    else
    {
        A|=pot*c;
        solut(nod->fiu[c],p+1);
    }
}
int main ()
{
    f>>n;
    s[23]='a';
    i=0;
    insert(r,s);
    best=-1;
    for(i=1;i<=n;++i)
    {
        f>>x;
        S^=x;
        a=S;
        t=-1;
        while(a)
        {
            t++;
            if(a&1)
                s[t]=1;
            a>>=1;
        }
        for(j=0;j<=11;++j)
            swap(s[j],s[22-j]);
        A=0;
        pot=(1<<23);
        solut(r,s);
        cur=A^S;
        if(cur>best)
        { best=cur;st=poz;dr=i; }
		insert(r,s);
        memset(s,0,23);
    }
    g<<best<<" "<<st+1<<" "<<dr;
    return 0;
}