Cod sursa(job #791318)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 23 septembrie 2012 19:41:17
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb

#include <cstdio>

const int MAX_NUMBERS(100);
const int MAX_SUM(1000001);

int sum3 [MAX_SUM];
int numbers [MAX_NUMBERS];
int sums [MAX_NUMBERS] [MAX_NUMBERS] [MAX_NUMBERS];


inline bool binary_search (int x, int size)
{
	int left(0), right(size), middle((left + right) >> 1);
	while (left < right)
	{
		if (x > sum3[middle])
			left = middle + 1;
		else
			right = middle;
		middle = (left + right) >> 1;
	}
	return sum3[middle] == x;
}

inline void swap (int a, int b)
{
	sum3[a] ^= sum3[b];
	sum3[b] ^= sum3[a];
	sum3[a] ^= sum3[b];
}

inline void heap_down (int index, int size)
{
	int left((index >> 1) + 1), right(left + 1), largest;
	while (true)
	{
		if (left < size && sum3[left] > sum3[index])
			largest = left;
		else
			largest = index;
		if (right < size && sum3[right] > sum3[largest])
			largest = right;
		if (index == largest)
			break;
		swap(index,largest);
		index = largest;
		left = (index << 1) + 1;
		right = left + 1;
	}
}

inline void build_heap (int size)
{
	for (int i((size - 1) >> 1) ; i >= 0 ; --i)
		heap_down(i,size);
}

inline void heap_sort (int size)
{
	build_heap(size);
	--size;
	while (size)
	{
		swap(0,size);
		heap_down(0,size);
		--size;
	}
}

int main (void)
{
	std::freopen("loto.in","r",stdin);
	std::freopen("loto.out","w",stdout);
	int n, s;
	std::scanf("%d%d",&n,&s);
	int *iterator(numbers), *end(numbers + n);
	do
	{
		std::scanf("%d",iterator);
		++iterator;
	}
	while (iterator < end);
	std::fclose(stdin);
	iterator = sum3;
	int a, b, c, sum;
	for (a = 0 ; a < n ; ++a)
		for (b = a ; b < n ; ++b)
			for (c = b ; c < n ; ++c)
			{
				sum = numbers[a] + numbers[b] + numbers[c];
				sums[a][b][c] = sum;
				*iterator = sum;
				++iterator;
			}
	int size;
	size = iterator - sum3;
	heap_sort(size);
	int sum1, sum2;
	for (end = iterator, iterator = sum3 ; iterator < end ; ++iterator)
	{
		sum1 = s - *iterator;
		if (binary_search(sum1,size))
		{
			sum2 = *iterator;
			for (a = 0 ; a < n ; ++a)
				for (b = a ; b < n ; ++b)
					for (c = b ; c < n ; ++c)
						if (sums[a][b][c] == sum1 || sums[a][b][c] == sum2)
						{
							std::printf("%d %d %d ",numbers[a],numbers[b],numbers[c]);
							if (sums[a][b][c] == sum1)
							{
								sum1 = -1;
								if (sum2 == -1)
								{
									std::putchar('\n');
									std::fclose(stdout);
									return 0;
								}
							}
							else
							{
								sum2 = -1;
								if (sum1 == -1)
								{
									std::putchar('\n');
									std::fclose(stdout);
									return 0;
								}
							}
						}
		}
	}
	std::printf("-1\n");
	std::fclose(stdout);
	return 0;
}