Cod sursa(job #420598)

Utilizator GotenAmza Catalin Goten Data 19 martie 2010 23:40:43
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream>
using namespace std;
int b[1000100],a[110],h[1000100],s1[1000100],s2[1000100],s3[1000100],hh[110];
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);
}
void qsmic(int i, int j)
{
	int s=i,d=j,aux,piv=hh[(i+j)>>1];
	while(s<=d)
	{
		while(b[hh[s]]<b[piv])
			s++;
		while(b[hh[d]]>b[piv])
			d--;
		if(s<=d)
		{
			aux=hh[s];
			hh[s]=hh[d];
			hh[d]=aux;
			s++;
			d--;
		}
	}
	if(s<j)
		qsmic(s,j);
	if(i<d)
		qsmic(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];
		hh[i]=i;
	}
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(t=j;t<=n;t++)
			{
				b[++k]=a[hh[i]]+a[hh[j]]+a[hh[t]];
				h[k]=k;
				s1[k]=hh[i];
				s2[k]=hh[j];
				s3[k]=hh[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;
}