Cod sursa(job #455249)

Utilizator elfusFlorin Chirica elfus Data 13 mai 2010 12:00:54
Problema Loto Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<stdio.h>
struct  LOTO
{
	long x,y,z,s;
};
LOTO c[1000001];
long x[101];
long e[7];
long part(long st  , long dr)
{
	LOTO aux;
	long m,p,i,j;
	i=st-1;
	j=dr+1;
	m=(st+dr)/2;
	p=c[m].s;
	while (1)
	{
		do {++i;}while (c[i].s<p);
		do {--j;}while (c[j].s>p);
		if (i<j)
		{
			aux=c[i];
			c[i]=c[j];
			c[j]=aux;
		}
		else
			return  j;
	}
}
void quick (long st  , long dr)
{
	long sp;
	if (st<dr)
	{
		sp=part(st,dr);
		quick(st,sp);
		quick(sp+1,dr);
	}
}

long part1(long st  , long dr)
{
	long m,p,i,j,aux;
	i=st-1;
	j=dr+1;
	m=(st+dr)/2;
	p=e[m];
	while (1)
	{
		do {++i;}while (e[i]<p);
		do {--j;}while (e[j]>p);
		if (i<j)
		{
			aux=e[i];
			e[i]=e[j];
			e[j]=aux;
		}
		else
			return  j;
	}
}
void quick1(long st  , long dr)
{
	long sp;
	if (st<dr)
	{
		sp=part1(st,dr);
		quick1(st,sp);
		quick1(sp+1,dr);
	}
}


long cautbin(long st , long dr , long x)
{
	long m;
	while (st<=dr)
	{
		m=(st+dr)/2;
		if (c[m].s==x)
			return m;
		if (c[m].s>x)
			dr=m-1;
		else
			st=m+1;
	}
	return -1;
}


int main()
{
	long suma,n,i,j,k,u=0,m;
	
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	
	scanf("%ld%ld",&n,&suma);
	for (i=1;i<=n;i++)
		scanf("%ld",&x[i]);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++)
			{
				c[++u].x=x[i];
				c[u].y=x[j];
				c[u].z=x[k];
				c[u].s=x[i]+x[j]+x[k];
			}
	quick(1,u);
	for (i=1;i<=u;i++)
	{
		if (c[i].s<suma)
			{m=cautbin(1,u,suma-c[i].s);
			if (m!=-1)
				break;
			}
	}
	if (m!=-1 && i<=u && c[i].s+c[m].s==suma)
	{
		e[1]=c[i].x;
		e[2]=c[i].y;
		e[3]=c[i].z;
		e[4]=c[m].x;
		e[5]=c[m].y;
		e[6]=c[m].z;
		quick1(1,6);
		for (i=1;i<=6;i++)  printf("%ld ",e[i]);
		printf("\n");  return 0;
	}
	printf("-1\n");return 0;
}