Cod sursa(job #402349)

Utilizator avram_florinavram florin constantin avram_florin Data 23 februarie 2010 20:05:35
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<cstdio>
#include<cstring>
#define MAXN 1000001

int n,nr,v[101],heap[MAXN];
long long S;
typedef struct{
			int i,j,k;
			}point;
point A[MAXN];

void sift(int heap[],int n,int k)
{
	int son,aux;
	point a;
	do
	{
		son=0;
		if(2*k<=n)
			{
				son=2*k;
				if(2*k+1<=n&&heap[2*k]<heap[2*k+1])
					son=2*k+1;
				if(heap[son]<=heap[k])
					son=0;
			}
		if(son)
			{
				aux=heap[son];
				heap[son]=heap[k];
				heap[k]=aux;
				a=A[son];
				A[son]=A[k];
				A[k]=a;
				k=son;
			}
	}
	while(son);
}

void build_heap(int heap[],int n)
{
	int i;
	for(i=n/2;i;i--)
		sift(heap,n,i);
}

void heapsort()
{
	int i,aux;
	point a;
	for(i=n;i>=2;i--)
		{
			aux=heap[1];
			heap[1]=heap[i];
			heap[i]=aux;
			a=A[1];
			A[1]=A[i];
			A[i]=a;
			sift(heap,i-1,1);
		}
}

int caut_bin(int li,int ls,int s)
{
	int m=(li+ls)>>1;
	while(li<=ls)
		{
			m=(li+ls)>>1;
			if(heap[m]==s)
				return m;
				else
				if(heap[m]>s)
					ls=m-1;
					else
					li=m+1;
		}
	return 0;
}

int main ()
{
	freopen("loto.in" , "r" , stdin);
	freopen("loto.out" , "w" , stdout);
	scanf("%d", &nr);
	scanf("%lld" , &S);
	int i,j,k;
	for(i=1;i<=nr;i++)
		scanf("%d" , &v[i]);
	for(i=1;i<=nr;i++)
		for(j=i;j<=nr;j++)
			for(k=j;k<=nr;k++)
				{
					heap[++n]=v[i]+v[j]+v[k];
					A[n].i=i;
					A[n].j=j;
					A[n].k=k;
				}
	build_heap(heap,n);
	heapsort();
	int sum,ok;
	for(i=1;i<=n;i++)
		{
			sum=S-heap[i];
			ok=caut_bin(1,n,sum);
			if(ok)
				{
					printf("%d %d %d %d %d %d\n" , v[A[i].i] , v[A[i].j] , v[A[i].k] , v[A[ok].i] , v[A[ok].j] , v[A[ok].k]);
					return 0;
				}
		}
	printf("-1\n");
	return 0;
}