Cod sursa(job #548)

Utilizator darklordHabalau Andrei darklord Data 11 decembrie 2006 15:25:22
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
#define dim 1000002

long n,s,i,a[dim],j,l,k,ind;

void qsort(long ls,long ld);

int imp(long ls,long ld);
int cauta(long s);
struct sir
{	long a,b,c,s;
}x[dim];

int main()
{	freopen ("loto.in","r",stdin);
	freopen ("loto.out","w",stdout);
	scanf("%ld%ld",&n,&s);
	for(i=0;i<n;i++)
		scanf("%ld",&a[i]);
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			for(l=0;l<n;++l)
			{   x[++k].s=a[i]+a[j]+a[l];
				x[k].a=a[i];x[k].b=a[j];x[k].c=a[l];
			}
	qsort(1,k);
	for(i=1;i<=k;i++)
	{   long c=cauta(s-x[i].s);
		if(c)
		{	printf("%ld %ld %ld %ld %ld %ld",x[i].a,x[i].b,x[i].c,x[c].a,x[c].b,x[c].c);
			ind=1;
			break;
		}
	}
	if(ind==0)
		printf("-1");
	fclose(stdin);fclose(stdout);
	return 0;
}

void qsort(long ls,long ld)
{	int poz=imp(ls,ld);
	if(poz-1>ls)
		qsort(ls,poz-1);
	if(ld>poz+1)
		qsort(poz+1,ld);
}

int imp(long ls,long ld)
{   int dir,ii=0,jj=-1;
	while(ls<=ld)
	{	if(x[ls].s>x[ld].s)
		{   sir aux=x[ls];
			x[ls]=x[ld];
			x[ld]=aux;
			dir=ii;
			ii=-jj;
			jj=-dir;
		}
		ls+=ii;ld+=jj;
	}
	return ls;
}

int cauta(long s)
{   long ls=1,ld=k;

	while(ls<ld)
	{
		long c=(ls+ld)/2;
		if(x[c].s==s)
			return c;
		else
			if(x[c].s>s)
				ld=c-1;
			else
				ls=c+1;
	}
	return 0;
}