Cod sursa(job #610685)

Utilizator SteveStefan Eniceicu Steve Data 28 august 2011 18:42:23
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <algorithm>

using namespace std;

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 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)
		{
			auxil = v[l1];
			v[l1] = v[l2];
			v[l2] = auxil;
			if (pivot)
			{
				l2--;
				pivot = 0;
			}
			else
			{
				l1++;
				pivot = 1;
			}
		}
		else
		{
			if (pivot) l1++;
			else l2--;
		}
	}
	qsort (l1a, l1 - 1);
	qsort (l1 + 1, l2a);
}

inline int cmp (elem x, elem y)
{
	return x.Suma < y.Suma;
}

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--;
			}
		}
	}
	//qsort (0, l);
	sort (v + 1, v + l, cmp);
	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;
}