Cod sursa(job #2058299)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 5 noiembrie 2017 14:14:02
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream fi("xormax.in");
ofstream fo("xormax.out");
typedef struct trie {bool terminal;struct trie * fiu[2];} NOD, *TRIE;

void adauga(TRIE &T, char *p)
/// se adauga X in T
{
    if (T==NULL)
    {
        T=new NOD;
        T->terminal=false;
        for (int i=0;i<=1;i++)
            T->fiu[i]=NULL;
        adauga(T,p);
    }
    if ((*p)=='\0')
        T->terminal=true;
    else
    {
        T->terminal=false;
        adauga(T->fiu[(*p)-'0'],p+1);
    }
}

void cauta(TRIE T, char *p, int &rez)
/// p este sirul fata de care ma opun
{
    if (T->terminal==true)
        return;
    if (*p=='0')
        if (T->fiu[1]!=NULL)
        {
            rez=rez*2+1;
            cauta(T->fiu[1],p+1,rez);
        }
        else
        {
            rez=rez*2;
            cauta(T->fiu[0],p+1,rez);
        }
    else
        if (T->fiu[0]!=NULL)
        {
            rez=2*rez;
            cauta(T->fiu[0],p+1,rez);
        }
        else
        {
            rez=2*rez+1;
            cauta(T->fiu[1],p+1,rez);
        }
}

TRIE T;
int N;
int A[100001];
int X[100001];
char B[23];
int k,v,dr,rez,val,ind,ind2;
int main()
{
    fi>>N;
    for (int i=1;i<=N;i++)
    {
        fi>>A[i];
        X[i]=X[i-1]^A[i];
    }
    T=new NOD;
    T->terminal=true;
    T->fiu[0]=T->fiu[1]=NULL;
    rez=-1;
    for (int i=1;i<=N;i++)
    {
        /// se introduce numarul corespunzator lui X[i] in trie-ul T
        /// se obtin siruri de cate 21 de biti
        memset(B,'0',sizeof(B));
        if(X[i]==0)
            B[21]='\0';
        else
        {
            B[21]='\0';
            dr=20;
            val=X[i];
            while(val)
            {
                B[dr]=(char)(val%2+'0');
                dr--;
                val/=2;
            }
        }
        val=0;
        cauta(T,B,val);
        adauga(T,B);
        val^=X[i];
        if(val>rez)
        {
            rez=val;
            ind=i;
        }
    }
    fo<<rez<<" ";
    for(int i=0; i<ind; i++)
    {
        if((X[i]^X[ind])==rez)
        {
            ind2=i+1;
        }
    }
    fo<<ind2<<" "<<ind<<"\n";
    fi.close();
    fo.close();
    return 0;
}