Cod sursa(job #2010907)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 14 august 2017 18:31:01
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#define nmax 100001
using namespace std;
fstream f1 ("xormax.in", ios::in);
fstream f2 ("xormax.out", ios::out);
long int n, maxi=-1, st, dr, p[21];
struct trie
{
    trie * ch[2];
    long int in;///indicele i al lui xi, doar pe final de cuv
}* rad;
void init_trie(trie *&t)
{
    t=new trie;
    t->ch[0]=0;
    t->ch[1]=0;
    t->in=0;
}
void puteri()
{
    int i;
    p[0]=1;
    for(i=1; i<=20; i++)
        p[i]=p[i-1]*2;
}
void cauta(trie *nod, long int val, long int in, long int rez, int nrbit)
{
    if(nrbit>=0)
    {
        if((p[nrbit]&val))
        {
         if(nod->ch[0]!=0) {rez+=p[nrbit]; cauta(nod->ch[0], val, in, rez,nrbit-1);}
         else if(nod->ch[1]!=0)            cauta(nod->ch[1], val, in,rez, nrbit-1);
        }
        else
        {
          if(nod->ch[1]!=0) {rez+=p[nrbit]; cauta(nod->ch[1], val, in, rez,nrbit-1);}
          else if(nod->ch[0]!=0)            cauta(nod->ch[0], val, in,rez, nrbit-1);
        }
    }
    else
    {
        if(maxi<rez) {maxi=rez;st=nod->in+1; dr=in;}
        else if((maxi==rez)&&(dr> in)) {st=nod->in+1; dr=in;}
        else if((maxi==rez)&&(in- (nod->in+1)< dr-st)&&(dr>=in)) {st=nod->in+1; dr=in;}
    }
}
void insert_trie(trie *nod, long int val, int nrbit, long int in)
{
    if(nrbit>=0)
    {
        if((val&p[nrbit])==0)
        {
            if(nod->ch[0]==0) init_trie(nod->ch[0]);
            insert_trie(nod->ch[0], val, nrbit-1, in);
        }
        else
        {
            if(nod->ch[1]==0) init_trie(nod->ch[1]);
            insert_trie(nod->ch[1], val, nrbit-1, in);
        }
    }
    else nod->in=in;   ///pe ultimul nod pui indicele corespunzator
}
int main()
{
    long int i, sum=0, x;
    f1>>n;
    init_trie(rad);
    puteri();
    for(i=1; i<=n; i++)
    {
        f1>>x;
        sum^=x; ///sum=xi, capatul drept=i

        if(maxi<sum) {maxi=sum; st=1; dr=i;}
        else if((maxi==sum)&&(dr>i)) {st=1; dr=i;}
             else if((maxi==sum)&&(dr-st> i-1)&&(dr>=i)) {st=1; dr=i;}

        insert_trie(rad, sum, 20, i); ///inserezi in trie val x in baza 2,20= nr bit analizat curent
        cauta(rad, sum, i, 0, 20);        ///cauti in trie un string(implicit xj in baza 2, j<i) a.i xi^xj maxim si actualizezi maxi cu xi^xj
    }

    f2<<maxi<<" "<<st<<" "<<dr;
    return 0;
}