Pagini recente » Cod sursa (job #758879) | Cod sursa (job #1066941) | Cod sursa (job #670545) | Cod sursa (job #2006014) | Cod sursa (job #1755249)
#include <algorithm>
#include <fstream>
#include <tuple>
#include <vector>
#define MAKE_IT_FASTER 1
int main() {
int N, S;
std::vector<int> numbers;
std::vector<int> solution;
std::vector<std::tuple<int, int, int, int>> combinations;
std::ifstream fin("loto.in");
std::ofstream fout("loto.out");
fin >> N >> S;
numbers.resize(N);
for (size_t i = 0; i < numbers.size(); i++)
fin >> numbers[i];
std::sort(numbers.begin(), numbers.end());
for (size_t i = 0; i < numbers.size(); i++)
for (size_t j = i; j < numbers.size(); j++)
for (size_t k = j; k < numbers.size(); k++)
combinations.push_back(std::make_tuple(
numbers[i] + numbers[j] + numbers[k], numbers[i], numbers[j],
numbers[k]));
std::sort(combinations.begin(), combinations.end());
#ifdef MAKE_IT_FASTER
for (size_t i = 0, j = combinations.size() - 1; i <= j; i++) {
for (; i <= j &&
std::get<0>(combinations[i]) + std::get<0>(combinations[j]) > S; -- j);
if (i <= j &&
std::get<0>(combinations[i]) + std::get<0>(combinations[j]) == S) {
solution.insert(solution.begin(),
{std::get<1>(combinations[i]),
std::get<2>(combinations[i]),
std::get<3>(combinations[i]),
std::get<1>(combinations[j]),
std::get<2>(combinations[j]),
std::get<3>(combinations[j])});
break;
}
}
#else
for (size_t i = 0; i < numbers.size() && !solution.size(); i++)
for (size_t j = i; j < numbers.size() && !solution.size(); j++)
for (size_t k = j; k < numbers.size() && !solution.size(); k++) {
int sum = S - numbers[i] - numbers[j] - numbers[k];
auto iter = std::lower_bound(
combinations.begin(), combinations.end(),
std::make_tuple(sum, 0, 0, 0));
if (sum == std::get<0>(*iter)) {
solution.insert(solution.begin(),
{numbers[i], numbers[j], numbers[k],
std::get<1>(*iter), std::get<2>(*iter),
std::get<3>(*iter)});
}
}
#endif
std::sort(solution.begin(), solution.end());
for (auto e : solution)
fout << e << " ";
if (!solution.size())
fout << "-1";
fout << std::endl;
return 0;
}