Cod sursa(job #1755249)

Utilizator crushackPopescu Silviu crushack Data 9 septembrie 2016 17:19:22
Problema Loto Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 2.3 kb
#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;
}