Cod sursa(job #610650)

Utilizator SteveStefan Eniceicu Steve Data 28 august 2011 14:52:39
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <fstream.h>

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

typedef struct elem
{
	long Suma;
	long unu;
	long doi;
	long trei;
};

long i, N, S, vector[101], l = -1, gata = 0;
elem v[1000001], auxil;

void quickSort(elem *arr, int elements)
{
	#define  MAX_LEVELS  300
	int  piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R, swap ;
	beg[0]=0;
	end[0]=elements;
	while (i>=0)
	{
		L=beg[i];
		R=end[i]-1;
		if (L<R)
		{
      			piv=arr[L].Suma;
			while (L<R)
			{
				while (arr[R].Suma>=piv && L<R) R--;
				if (L<R) memcpy (&arr[L++], &arr[R], sizeof (elem));
				while (arr[L].Suma<=piv && L<R) L++;
				if (L<R) memcpy (&arr[R--], &arr[L], sizeof(elem));
			}
			arr[L].Suma=piv;
			beg[i+1]=L+1;
			end[i+1]=end[i];
			end[i++]=L;
			if (end[i]-beg[i]>end[i-1]-beg[i-1])
			{
				swap=beg[i];
				beg[i]=beg[i-1];
				beg[i-1]=swap;
				swap=end[i];
				end[i]=end[i-1];
				end[i-1]=swap;
			}
		}
		else
		{
			i--;
		}
	}
}

/*void qsort (long l1, long l2)
{
	long l1a = l1, l2a = l2, pivot = 0;
	if (l1 >= l2) return;
	while (l1 < l2)
	{
		if (v[l1].Suma > v[l2].Suma)
		{
			memcpy (&auxil, &v[l1], sizeof (elem));
			memcpy (&v[l1], &v[l2], sizeof (elem));
			memcpy (&v[l2], &auxil, sizeof (elem));
			if (pivot)
			{
				l2--;
				pivot = 0;
			}
			else
			{
				l1++;
				pivot = 1;
			}
		}
		else
		{
			if (pivot) l1++;
			else l2--;
		}
	}
	qsort (l1a, l1 - 1);
	qsort (l1 + 1, l2a);
}*/

int main ()
{
	fin >> N >> S;
	for (i = 0; i < N; i++)
	{
		fin >> vector[i];
	}
	fin.close ();
	long j, k;
	for (i = 0; i < N; i++)
	{
		for (j = i; j < N; j++)
		{
			for (k = j; k < N; k++)
			{
				v[++l].Suma = (v[l].unu = vector[i]) + (v[l].doi = vector[j]) + (v[l].trei = vector[k]);
				if (v[l].Suma > S) l--;
			}
		}
	}
	quickSort (v, l + 1);
	long aux, h, step;
	for (i = 0; i <= l; i++)
	{
		aux = S - v[i].Suma;
		for (step = 1; step < l; step <<= 1);
		for (h = 0; step; step >>= 1)
		{
			if (h + step < l && v[h + step].Suma <= aux) h += step;
		}
		if (v[h].Suma == aux)
		{
			fout << v[i].unu << " " << v[i].doi << " " << v[i].trei << " " << v[h].unu << " " << v[h].doi << " " << v[h].trei;
			fout.close ();
			return 0;
		}
	}
	fout << "-1";
	fout.close ();
	return 0;
}