Cod sursa(job #138197)

Utilizator za_wolfpalianos cristian za_wolf Data 17 februarie 2008 22:53:01
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 101
#define MMAX 1000001
using namespace std;
long M,z[MMAX],s,in,sf,y[MMAX],x[NMAX],i,j,n,m,k,l,w;
struct kkt
{
long a,b,c;
};
kkt q[MMAX]/*,Q[MMAX]*/;
struct coi
{
	long Y,Z;
};
coi sfarsit[MMAX];
int N,  B[MMAX],C[MMAX];
/*void merge_sort(int l, int r)
{
  int m = (l + r) >> 1, i, j, k;
  if (l == r) return;
	   merge_sort(l, m);
	   merge_sort(m + 1, r);
	   for (i=l, j=m+1, k=l; i<=m || j<=r; )
		   if (j > r || (i <= m && y[i] < y[j]))
		   {
			   B[k++] = y[i++];
			   C[k-1]=z[i-1];
		   }
		   else
		   {
			   B[k++] = y[j++];
			   C[k-1]=z[j-1];
		   }
	   for (k = l; k <= r; k++)
	   {
			y[k] = B[k];
			z[k]=C[k];
	   }
}
*/

int cmpf(const coi a,const coi b)
{
	return a.Y>b.Y;
}

int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%ld%ld",&n,&k);
	for (i=1;i<=n;i++)
		scanf("%ld",&x[i]);

	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (l=1;l<=n;l++)
			{
				y[++y[0]]=x[i]+x[j]+x[l];
				q[y[0]].a=x[i];
				q[y[0]].b=x[j];
				q[y[0]].c=x[l];
				z[y[0]]=y[0];
				sfarsit[y[0]].Y=y[y[0]];
				sfarsit[y[0]].Z=z[y[0]];

			}
   M=y[0];
	y[0]=0;
//	merge_sort(1,y[0]);
	sort(y+1,y+n+1,cmpf);
	for (i=1;i<=M;i++)
	{
		y[i]=sfarsit[i].Y;
		z[i]=sfarsit[i].Z;
		s=k-y[i];
		in=1;
		sf=M;
		while (in<=sf)
		{
			l=(in+sf)/2;
			if (y[l]==s) {printf("%ld %ld %ld %ld %ld %ld\n",q[z[i]].a,q[z[i]].b,q[z[i]].c,q[z[l]].a,q[z[l]].b,q[z[l]].c); return 0;}
			if (y[l]<s) in=l+1;
			else
			sf=l-1;
		}

	}
	printf("-1\n");
	return 0;
}