Cod sursa(job #120061)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 4 ianuarie 2008 09:42:47
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<stdio.h>
long n,ss,s[1000000],i,i1,i2,a[111],j,aa,nn;long x[1000000],x1[1000000],x2[1000000],poz,st,dr,m;
int partit(long a[ ],long x[ ],long x1[ ],long x2[ ],long st, long dr)
{int i,j,m,piv,aa;
 m=(st+dr)/2;
 piv=a[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(a[i]<piv);
   do{--j;} while(a[j]>piv);
   if (i<j)
	 {aa=a[i];a[i]=a[j];a[j]=aa;aa=x[i];x[i]=x[j];x[j]=aa;aa=x1[i];x1[i]=x1[j];x1[j]=aa;aa=x2[i];x2[i]=x2[j];x2[j]=aa;}
	   else
	 return j;
  }
}
void quicks(long a[ ],long x[ ],long x1[ ],long x2[ ],long st,long dr)
{int p;
 if (st<dr)
   {p=partit(a,x,x1,x2,st,dr);
	quicks(a,x,x1,x2,st,p);
	quicks(a,x,x1,x2,p+1,dr);
   }
}

int main()
{
freopen("loto.in","r",stdin);
freopen("loto.out","w",stdout);
scanf("%ld %ld",&n,&ss);
s[0]=0;
for(i=1;i<=n;++i)
  scanf("%ld",&a[i]);
nn=0;
for(i=1;i<=n;++i)
   for(i1=1;i1<=n;++i1)
      for(i2=1;i2<=n;++i2)
	 {s[++nn]=a[i]+a[i1]+a[i2];x[nn]=i;x1[nn]=i1;x2[nn]=i2;}
quicks(s,x,x1,x2,1,nn);
//for(i=1;i<nn;++i)
//   for(j=i+1;j<=nn;++j)
//      if(s[i]>s[j]){aa=x1[i];x1[i]=x1[j];x1[j]=aa;aa=x2[i];x2[i]=x2[j];x2[j]=aa;aa=x[i];x[i]=x[j];x[j]=aa;aa=s[i];s[i]=s[j];s[j]=aa;}
poz=-1;
for(i=1;i<=nn;++i)
   {st=1;dr=nn;
    while(st<=dr)
	 {m=(st+dr)/2;
	  if (s[m]+s[i]==ss) {poz=m; break;}
		  else if (s[m]+s[i]>ss) dr=m-1;
				    else st=m+1;
	 }
    if(poz>=0) {printf("%ld %ld %ld %ld %ld %ld",a[x[i]],a[x1[i]],a[x2[i]],a[x[poz]],a[x1[poz]],a[x2[poz]]);break;}
   }
if(poz==-1) printf("-1");
fcloseall();
return 0;
}