Cod sursa(job #2066875)

Utilizator patcasrarespatcas rares danut patcasrares Data 15 noiembrie 2017 17:16:15
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n,a,poz,rs,rd,ma=-1,y[35];
char s[35];
struct trie
{
    int st=0;
    trie *urm[2]={0};
};
trie *t=new trie;
void inserare(trie *nod,char *s,int k,int p)
{
    if(*s==0)
    {
        nod->st=max(nod->st,k);
        return;
    }
    int v=*s-'0';
    if(y[p]==-1)
        v=1-v;
    if(nod->urm[v]==0)
        nod->urm[v]=new trie;
    inserare(nod->urm[v],s+1,k,p+1);
}
void cauta(trie *nod,int k,int nr,int p)
{
    if(p==21)
    {
        if(nr==ma)
            if(k==rd)
                if(nod->st>rs)
                {
                    ma=nr;
                    rs=nod->st;
                    rd=k;
                }
        if(nr>ma)
        {
            ma=nr;
            rs=nod->st;
            rd=k;
        }
        return;
    }
    if(y[p]==-1)
    {
        if(nod->urm[0])
            cauta(nod->urm[0],k,nr*2+1,p+1);
        else
            cauta(nod->urm[1],k,nr*2,p+1);
        return;
    }
    if(nod->urm[1])
        cauta(nod->urm[1],k,nr*2+1,p+1);
    else
        cauta(nod->urm[0],k,nr*2,p+1);
}
int main()
{
    fin>>n;
    for(int i=0;i<21;i++)
        y[i]=1;
    for(int i=1;i<=n;i++)
    {
        fin>>a;
        if(a>ma)
        {
            ma=a;
            rs=rd=i;
        }
        poz=20;
        do
        {
            if(a%2==1)
            {
                s[poz]='1';
                y[poz]=-y[poz];
            }
            else
                s[poz]='0';
            a/=2;
            poz--;
        }while(a);
        s[21]='\0';
        if(poz!=-1)
            for(int j=0;j<=poz;j++)
                s[j]='0';
        if(i!=1)
            cauta(t,i,0,0);
        inserare(t,s,i,0);
    }
    fout<<ma<<' '<<rs<<' '<<rd;
}