Cod sursa(job #602731)

Utilizator MirceaD85Mircea Digulescu MirceaD85 Data 12 iulie 2011 18:35:26
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream.h>

#define MAXC 1024000

struct nod
{
 int end;
 long l0,r1;
} nodes[MAXC];
long root=0, K=0;

int n;

#define MAXP 22
long pow2[MAXP];

ifstream in("xormax.in");
ofstream out("xormax.out");

long newnode(int end)
{
 K++;
 nodes[K].l0=nodes[K].r1=-1;
 nodes[K].end = end;
};

void InsertX(unsigned long XoR, int end)
{
 int i, is1; 
 nod r = nodes[root];
 for(i=20;i>0;i--)
  { 
    is1 = ((XoR & pow2[i]) > 0);
    if(is1) 
     {
      if(nodes[r].r1!=-1)
        r=nodes[r].r1;
      else
        r=nodes[r].r1=newnode(-2);
     }
    else
     {
      if(nodes[r].l0!=-1)
       r=nodes[r].l0;
      else
       r=nodes[r].l0=newnode(-2);
     }
  }
 is1 = ((XoR & pow2[0])>0);
 if(is1)
  r=nodes[r].r1=newnode(end);
 else
  r=nodes[r].l0=newnode(end);
};

struct Fres
{
 int end;
 unsigned long val;
};

Fres FindX(unsigned long best)
{
 unsigned long vl = 0; 
 nod r = nodes[root];
 for(i=20;i>0;i--)
  { 
    is1 = ((best & pow2[i]) > 0);
    is1 = 1 - is1;
    if(is1) 
     {
      if(nodes[r].r1!=-1)
        {r=nodes[r].r1; vl += pow2[i];}
      else
        {r=nodes[r].l0; vl += 0; }
     }
    else
     {
      if(nodes[r].l0!=-1)
       { r=nodes[r].l0; vl += pow2[i]; }
      else
       { r=nodes[r].r1; vl += 0; }
     }
  }
 Fres res;
 res.val = vl;
 res.end = r.end;
}

int main()
{
 in>>n;
 int i;
 pow2[0]=1;
 for(i=1;i<MAXP;i++)
  pow2[i]=pow2[i-1]*2;

 InsertX(0,-1);
 unsigned long XoRcur = 0;
 unsigned long opt = -1;
 int start = -1;
 int end = -1;
 for(i=0;i<n;i++)
  {
   unsigned long x;
   in>>x;
   XoRcur = XoRcur ^ x;
   FRes R = FindX(~XoRcur);
   if(R.val > opt) 
    {
     opt = R.val;
     start = R.end+1;
     end = i;
    }
   InsertX(XoRcur, i);
  }
 out<<opt<<" "<<start+1<<" "<<end+1<<"\n";
 return 0;
}