Cod sursa(job #138673)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 18 februarie 2008 23:43:43
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <stdio.h>
#include <math.h>
#define MAX 100100


const long xx[30]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608};
int a[MAX][25],sir[MAX],n,kkt[MAX];
long S=0,inc,sf;

void citire()
{
   long x;
   freopen ("xormax.in","r",stdin);
      scanf("%d",&n);
      for (int i=0;i<n;i++)
      {
	  scanf("%d",&sir[i]);
/*	  x=sir[i];
	  long j=22;
	  while (x)
	  {
	     if (x>=pow(2,j))
	     {
		a[i][j]=1;
		x-=pow(2,j);
	     }
	    j--;
	  }  */
      }
fclose(stdin);
}

int xorr (int a[25],int b[25])
{
  int c[25];
  long S1=0;
   for (int j=0;j<22;j++)
   {
       c[j]=a[j];
       if (a[j]==1)
	  S1+=xx[j];
   }

   long S=0;
   for (int i=0;i<22;i++)
   {
      if (a[i]!=b[i])
      {
	 a[i]=1;
	 S+=xx[i];
      }
      else
	a[i]=0;
   }

   if (S1>S)
   {
	   for (int k=0;k<22;k++)
	      a[k]=c[k];
      return S1;
   }
   return S;
}

long maxim (long a,long b)
{
   if (a>b)
      return a;
      return b;
}
void max()
{
   long max=sir[0];
   freopen ("xormax.out","w",stdout) ;
/*   for (int i=1;i<n;i++)
   {
      aux=xorr(a[i],a[i-1]);
      if (aux>sir[i])
      {
	 kkt[i]=kkt[i-1]+1;
	 if (aux>max)
	 {
	    max=aux;
	    sf=i;
	    inc=i-kkt[i]+1;
	 }
      }
      else
      {
	 kkt[i]=1;
	   if (aux>max)
	   {
	      max=aux;
	      sf=i;
	      inc=i;
	   }

      }
   }                  */
   for (int q=0;q<n;q++)
       kkt[q]=1;

   for (int i=1;i<n;i++)
   {
      if (sir[i]>max)
      {
	 max=sir[i];
	 inc=i;
	 sf=inc+kkt[i]-1;
      }

      if ((sir[i]^sir[i-1])>max)
      {
	 max=sir[i]^sir[i-1];
	 sir[i]=max;
	 inc=i-1;
	 sf=inc+kkt[i];
	 kkt[i]++;
      }
   }
   printf ("%ld %ld %ld \n",max,inc+1,sf+1);
   fclose (stdout);
}

int main ()
{
   citire();
   max();
   return 0;
}