Cod sursa(job #156532)

Utilizator roquerMarinescu Liana roquer Data 12 martie 2008 16:52:33
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<stdio.h>
#include<stdlib.h>
#define N 1000001
int n,s,av[N],k1,poz[N];
struct vec
{
	int i,j,k,s;
}v[N],aux;
void read()
{
	int i;
	scanf("%d%d",&n,&s);
	for(i=1;i<=n;i++)
		scanf("%d",&av[i]);
}
int maxim(const void *a,const void *b)
{
	int aa,bb;
	aa=*(int*)a;
	bb=*(int*)b;
	return v[poz[aa]].s-v[poz[bb]].s;
}
/*
int binary_search(int val)  
{  
    int i, step;  
    for (step = 1; step <= k1; step <<= 1);  
    for (i = 0; step; step >>= 1)  
        if (i + step <= k1 && v[poz[i] + step].s <= val)  
           i += step;  
    return poz[i];
}
*/
void solve()
{
	int i,a,b,j,k,sol,mij,sum;
	for(i=1;i<=n;++i)
		for(j=i;j<=n;++j)
			for(k=j;k<=n;++k)
			{
				v[++k1].i=av[i];
				v[k1].j=av[j];
				v[k1].k=av[k];
				sum=av[i]+av[j]+av[k];
				v[k1].s=sum;
				poz[k1]=k1;
			}
	qsort(poz+1,k1,sizeof(poz[0]),maxim);
	for(i=1;i<=k1;++i)
	{
		sol=s-v[i].s;
		/*mij=binary_search(sol);
		if(v[mij].s==sol)
		{
			printf("%d %d %d %d %d %d\n",v[i].i,v[i].j,v[i].k,v[mij].i,v[mij].j,v[mij].k);
			return;
		}
		*/
		a=1;
		b=k1;
		while(a<=b)
		{
			mij=(a+b)/2;
			if(v[poz[mij]].s==sol)
			{
				printf("%d %d %d %d %d %d\n",v[i].i,v[i].j,v[i].k,v[poz[mij]].i,v[poz[mij]].j,v[poz[mij]].k);
				return;
			}
			if(sol<v[poz[mij]].s)
				b=mij-1;
			else
				a=mij+1;
		}
	}
	printf("-1\n");
}
int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	read();
	solve();
	return 0;
}