Cod sursa(job #412845)

Utilizator avram_florinavram florin constantin avram_florin Data 6 martie 2010 17:33:41
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<fstream>
#include<algorithm>
#define NMAX 500000

using namespace std;
ifstream fin ("loto.in");
ofstream fout ("loto.out");

int m,n,v[101];
long long S,sum;

typedef struct{
			int i,j,k,s;
			}loto;
loto l[NMAX];

void sift(loto l[],int n , int k)
{
	int son;
	loto aux;
	do
	{
		son = 0;
		if( 2*k <=n )
			{
				son = 2*k;
				if(2*k+1 <= n && l[2*k+1].s > l[2*k].s)
					son = 2*k+1;
				if(l[son].s <= l[k].s)
					son = 0;
			}
		if(son)
			{
				aux = l[son];
				l[son] = l[k];
				l[k] = aux;
				k = son;
			}
	}while(son);
}

void build_heap(int n)
{
	int i;
	for(i = n/2 ; i ; i--)
		sift(l,n,i);
}

void heapsort()
{
	int i;
	loto aux;
	for(i = n ; i >= 2 ; i--)
		{
			aux = l[i];
			l[i] = l[1];
			l[1] = aux;
			sift(l,i-1,1);
		}
}

/*int bs(int val)
{
	int i , step;
	for( step = 1 ; step < n ; step <<=1 );
	for(i = 0 ; step ; step >>=1 )
		if( i + step < n && l[ i + step].s <= val )
			i += step;
	if(l[i].s == val )
		return i;
		else
		return 0;
}
*/

int bs(int val)
{
	int li,ls,m;
	li = 1;
	ls = n;

	while(li <= ls)
		{
			m = (li + ls) >> 1;
			if(l[m].s == val)
				return m;
				else
				if(l[m].s > val)
					ls = m - 1;
					else
					li = m + 1;
		}
	return 0;
}

void make_sum()
{
	int i , j ,k;
	for(i = 1 ; i <= m ; i++ )
		for(j = i ; j <= m ; j++)
			for(k = j ; k <= m ; k++)
				{
					l[++n].s = v[i] + v[j] + v[k];
					l[n].i = i;
					l[n].j = j;
					l[n].k = k;
				}
}

int main ()
{
	int i;
	fin >> m >> S;
	for( i = 1 ; i <= m ; i++)
		fin >> v[i] ;
	n = 0;
	make_sum();
	build_heap(n);
	heapsort();
	int poz;
	for(i = 1 ; i <= n ; i++ )
		{
			sum = S - l[i].s;
			poz = bs(sum);
			if(poz)
				{
					fout << v[l[i].i] <<' ' << v[l[i].j] <<' ' << v[l[i].k] <<' ' << v[l[poz].i] <<' ' << v[l[poz].j] <<' ' << v[l[poz].k] << '\n';
					return 0;
				}
		}
	fout << "-1\n" ;
	fin.close();
	fout.close();
	return 0;
}