Cod sursa(job #2066841)

Utilizator patcasrarespatcas rares danut patcasrares Data 15 noiembrie 2017 16:27:00
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 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;
char s[35];
struct trie
{
    int st=0;
    trie *urm[2]={0};
};
trie *t=new trie;
trie *as=new trie;
trie *b=new trie;
void inserare(trie *nod,char *s,int k)
{
    if(*s==0)
    {
        nod->st=max(nod->st,k);
        return;
    }
    if(nod->urm[*s-'0']==0)
        nod->urm[*s-'0']=new trie;
    inserare(nod->urm[*s-'0'],s+1,k);
}
void change(trie *nod,char *s,int k,int nr)
{
    if(*s==0)
    {
        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(*s=='1')
    {
        as=nod->urm[0];
        b=nod->urm[1];
        nod->urm[0]=b;
        nod->urm[1]=as;
    }
    if(nod->urm[0])
        change(nod->urm[0],s+1,k,nr*2);
    if(nod->urm[1])
        change(nod->urm[1],s+1,k,nr*2+1);
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a;
        y=a;
        if(a>ma)
        {
            ma=a;
            rs=rd=i;
        }
        poz=20;
        do
        {
            if(a%2==1)
                s[poz]='1';
            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&&y)
            change(t,s,i,0);
        inserare(t,s,i);
    }
    fout<<ma<<' '<<rs<<' '<<rd;
}