Cod sursa(job #420594)

Utilizator GotenAmza Catalin Goten Data 19 martie 2010 23:31:01
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<iostream>
using namespace std;
int b[1000100],a[110],h[1000100],s1[1000100],s2[1000100],s3[1000100];
void qs(int i, int j)
{
	int s=i,d=j,aux,piv=h[(i+j)>>1];
	while(s<=d)
	{
		while(b[h[s]]<b[piv])
			s++;
		while(b[h[d]]>b[piv])
			d--;
		if(s<=d)
		{
			aux=h[s];
			h[s]=h[d];
			h[d]=aux;
			s++;
			d--;
		}
	}
	if(s<j)
		qs(s,j);
	if(i<d)
		qs(i,d);
}
int main()
{
	int n,s,k=0,i,j,t,l=1,x,S,ok=0,a1,a2;
	ifstream f("loto.in");
	ofstream g("loto.out");
	f>>n>>S;
	for(i=1;i<=n;i++)
		f>>a[i];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(t=1;t<=n;t++)
			{
				b[++k]=a[i]+a[j]+a[t];
				h[k]=k;
				s1[k]=i;
				s2[k]=j;
				s3[k]=t;
			}
	qs(1,k);
	while(l<k)
		l<<=1;
	for(i=1;i<=k&!ok&&b[h[i]]<S;i++)
	{
		x=S-b[h[i]];
		s=l;
		j=0;
		while(s&&!ok)
		{
			if(j+s<=k&&b[h[j+s]]<=x)
				j+=s;
			if(b[h[j]]==x)
			{
				a1=h[i];
				a2=h[j];
				ok=1;
			}			
			s>>=1;
		}
	}
	if(!ok)
		g<<"-1";
	else
		g<<a[s1[a1]]<<' '<<a[s2[a1]]<<' '<<a[s3[a1]]<<' '<<a[s1[a2]]<<' '<<a[s2[a2]]<<' '<<a[s3[a2]];
	return 0;
}