Cod sursa(job #138654)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 18 februarie 2008 23:15:21
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 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[MAX],int b[MAX])
{
   long S=0;
   for (int i=0;i<22;i++)
      if (a[i]!=b[i])
	 S+=xx[i];
   return S;
}

long maxim (long a,long b)
{
   if (a>b)
      return a;
      return b;
}
void max()
{
   long max=sir[0],aux=0;
   kkt[0]=1;
   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;
	   }

      }
   }
   printf ("%ld %ld %ld \n",max,inc+1,sf+1);
   fclose (stdout);
}

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