Pagini recente » Cod sursa (job #332042) | Cod sursa (job #2497116) | Monitorul de evaluare | Cod sursa (job #333983) | Cod sursa (job #791310)
Cod sursa(job #791310)
#include <cstdio>
#include <algorithm>
const int MAX_NUMBERS(100);
const int MAX_SUM(1000001);
int sum3 [MAX_SUM];
bool check [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);
std::sort(numbers,end);
if (*(iterator - 1) * 6 <= s)
goto Skip;
iterator = sum3;
int a, b, c, sum;
for (a = 0 ; a < n ; ++a)
for (b = 0 ; b < n ; ++b)
for (c = 0 ; c < n ; ++c)
{
sum = numbers[a] + numbers[b] + numbers[c];
sums[a][b][c] = sum;
if (check[sum])
continue;
check[sum] = true;
*iterator = sum;
++iterator;
}
int size;
size = iterator - sum3;
std::sort(sum3,sum3 + 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 = 0 ; b < n ; ++b)
for (c = 0 ; 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;
}
}
}
}
}
Skip :
std::printf("-1\n");
std::fclose(stdout);
return 0;
}