Cod sursa(job #1053010)

Utilizator sp3ct3rFMI Dima Robert sp3ct3r Data 12 decembrie 2013 00:44:44
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <algorithm>
#include <iostream>

using namespace std;
struct suma
{
	int val, a, b, p;
};

bool bin_cprer(suma, suma);
bool cprer(suma, suma);
int binFindPos = -1;
int main()
{
	int n, s;
	int *nr;
	suma *sume;
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);

	cin >> n >> s;
	nr = new int[n];
	sume = new suma[n*(n - 1) / 2 + n];
	for (int i = 0; i < n; ++i)
	{
		cin >> nr[i];
	}
	int ctr = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j < n; ++j)
		{
			sume[ctr].a = i;
			sume[ctr].b = j;
			sume[ctr].val = nr[i] + nr[j];
			sume[ctr].p = ctr;
			++ctr;
		}
	}

	sort(sume, sume + ctr, cprer);

	bool found = false;
	int result[6];
	for (int i = 0; i < ctr; ++i)
	{
		if (s - sume[i].val < 0)
			break;
		for (int j = i; j < ctr; ++j)
		{
			suma csum;
			csum.val = s - sume[i].val - sume[j].val;
			if (csum.val < 0)
			{
				break;
			}
			if (binary_search(sume, sume + ctr, csum, bin_cprer))
			{
				result[0] = nr[sume[i].a];
				result[1] = nr[sume[i].b];
				result[2] = nr[sume[j].a];
				result[3] = nr[sume[j].b];

				result[4] = nr[sume[binFindPos].a];
				result[5] = nr[sume[binFindPos].b];
				found = true;
				/*for (int k = 0; k < j; k++)
				{
				if (sume[k].val == csum.val)
				{
				result[4] = nr[sume[k].a];
				result[5] = nr[sume[k].b];

				break;
				}
				}*/
			}
			if (found) break;
		}
		if (found) break;
	}
	if (found)
	{
		sort(result, result + 6);
		for (int i = 0; i < 6; ++i)
		{
			cout << result[i] << " ";
		}
	}
	else cout << "-1";
}

bool bin_cprer(suma a, suma b)
{
	if (a.val == b.val)
	{
		if (a.p >= 0)
			binFindPos = a.p;
	}
	return a.val < b.val;
}

bool cprer(suma a, suma b)
{
	if (a.val < b.val)
	{
		return true;
	}
	else return false;
}