Cod sursa(job #2030387)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 1 octombrie 2017 15:58:14
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
using namespace std;
ifstream fi ("xormax.in");
ofstream fo ("xormax.out");
struct nod
{
  nod *st,*dr;
  int inceput;
  nod()
  {
    st=NULL;
    dr=NULL;
  }
};
nod *start;
int i,n,xorr,str,xormax,inc,sf;

void adaug(nod *&curent,int nr,int bit)
{
  if (curent==NULL) curent=new nod;
  if (bit==0)
  {
    curent -> inceput=i;
    return;
  }
  if (nr&bit)
    adaug(curent -> st,nr,bit/2);
  else
    adaug(curent -> dr,nr,bit/2);
}
void caut(nod *&curent,int nr,int bit)
{
  if (bit==0)
  {
    str=curent -> inceput;
    return;
  }
  if (nr&bit)
  {
    if (curent -> dr != NULL)
      caut(curent -> dr,nr,bit/2);
    else
      {
        xorr=(xorr^bit);
        caut (curent -> st,nr,bit/2);
      }
  }
  else
  {
    if (curent -> st != NULL)
      {
        xorr=(xorr^bit);
        caut(curent -> st,nr,bit/2);
      }
    else caut(curent -> dr,nr,bit/2);
  }
}
int main()
{
    fi>>n;
    start=new nod;
    int sum=0,x=0;
    adaug(start,0,(1<<22));
    for (i=1;i<=n;i++)
    {
      xorr=0;
      fi>>x;
      sum=(sum^x);
      caut(start,sum,(1<<22));
      adaug(start,sum,(1<<22));
      if (xormax<(xorr^sum))
      {
        xormax=(xorr^sum);
        sf=i;
        inc=str+1;
      }
      if (xormax==(xorr^sum)) inc=str+1;
    }
    fo<<xormax<<' '<<inc<<' '<<sf;
    return 0;
}