Cod sursa(job #96621)

Utilizator horiama1Mania Horia horiama1 Data 2 noiembrie 2007 15:01:03
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<stdio.h>
#include<stdlib.h>
#define N 500001
struct trei{
	int i,j,k;
};
int comp(const void *a,const void *b)
{
	trei *aa=(trei *)a,*bb=(trei *)b;
	trei x=*aa,y=*bb;
	if(x.i<y.i)
		return  -1;
	if(x.i==y.i)
		return 0;
    return 1;
}
int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	int i,j,k,n,s,q[100],t=0,w=0,x;
	trei v[N];
	scanf("%d%d",&n,&s);
	for(i=0;i<n;i++)
		scanf("%d",&q[i]);
	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
			for(k=j;k<n;k++)
			{
				v[t].i=q[i]+q[j]+q[k];
				v[t].j=q[i];
				v[t].k=q[j];
				t++;
			}
	qsort(v,n*n*n,sizeof(v[0]),comp);
	for(i=0;i<n*n*n;i++)
	{
		//x=n*n*n/2;t=0;
		/*
		while(v[x].i!=s-v[i].i&&t<=n*n*n/2)
		{
			if(v[x].i>s-v[i].i)
				x=x/2;
			if(v[x].i<s-v[i].i)
				x=(x+n*n*n)/2;
			t++;

		}
		*/
		int p=0,u=t-1,m;
		while(p<u){
			m=(p+u)/2;
			if(s-v[i].i<=v[m].i)
				u=m;
			else
				p=m+1;
		}
		if(v[p].i==s-v[i].i)
		{
			printf("%d %d %d %d %d %d",v[i].j,v[i].k,v[i].i-v[i].k-v[i].j,v[p].j,v[p].k,v[p].i-v[p].j-v[p].k);
			w=1;
			break;
		}
	}
	if(w==0)
		printf("-1");
	return 0;
}