Cod sursa(job #370810)

Utilizator DeadEyeNaiba Mihai Lucian DeadEye Data 2 decembrie 2009 12:30:36
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<algorithm>
#include<cstdio>
using namespace std;
struct s3
{
	int su,x,y,z;
}; //dushmi style
const int NN=1<<20;
s3 s[1000001];
int n,ss,q,poqi,poqj,k,a[102],v[7];
bool comp(const s3 &WTF, const s3 &OMG)
{
	if(WTF.su<OMG.su) return true;
	return false;
}
int cautb(int x)
{
	//PASPAS IN THE PAMPAS IN THE MOUNTAINS
	int i,pas=NN;
	for(i=0;pas;pas>>=1)
		if(i+pas<=q && s[i+pas].su<=x)
			i+=pas;
	if(s[i].su!=x)
		return 0;
	return i;
}
int main()
{
	int i,j,k;
    freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%d",&n,&ss);
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
	q=0;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{
				s[++q].su=a[i]+a[j]+a[k];
				s[q].x=a[i];
				s[q].y=a[j];
				s[q].z=a[k];
			}
	sort(s+1,s+q+1,comp);
	for(i=1;i<=q;++i)
	{
		poqj=cautb(ss-s[i].su);
		if(poqj!=0) poqi=i;
		if(poqi!=0 && poqj!=0) break;
	}
    if(poqi==0 && poqj==0) printf("-1");
    else	
	{
		v[1]=s[poqi].x;
		v[2]=s[poqi].y;
		v[3]=s[poqi].z;
		v[4]=s[poqj].x;
		v[5]=s[poqj].y;
		v[6]=s[poqj].z;
		sort(v+1,v+7);
		for(i=1;i<=6;++i)
			printf("%d ",v[i]);
	}
	return 0;
}