#include <array>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

// Define um template (molde) para a criação de funções que aceitam um vetor
// de algum tipo de elemento e retornam um array com os dois maiores elementos
// do vetor (maior na posição 0, menor na posição 1).
// Value é o nome que damos ao tipo dos elementos contidos no vetor, e que
// também é o tipo dos elementos do array retornado.
template <typename Value>
std::array<Value, 2> two_largest(std::vector<Value> v) {
  assert(v.size() >= 2); // Precisa pelo menos 2 elementos em v.

  // Estas variáveis precisam ter o mesmo tipo dos elementos de v.
  Value largest{v[0]};        // Terá o maior valor em v
  Value second_largest{v[1]}; // Terá o segundo maior valor em v

  // Inicializando largest e second_largest com v[0] e v[1]
  if (largest < second_largest) {
    std::swap(largest, second_largest);
  }

  // Percorre os outros elementos de v e atualiza largest e second_largest.
  // Pré-condição: Junção das seguintes condições:
  // (1) largest >= second_largest
  // (2) Para 0 <= j < 2, v[j] == largest || v[j] == second_largest
  for (size_t i = 2; i < v.size(); ++i) {
    // Invariante: Junção das seguintes condições:
    // (1) largest >= second_largest
    // (2) Para 0 <= j < i, v[j] <= largest
    // (3) Para 0 <= j < i, v[j] <= second_largest || v[j] == largest

    // Verifica se v[i] é um dos dois maiores.
    if (largest < v[i]) {
      // Se maior que largest, antigo largest agora é o segundo e v[i] é o maior
      // Por casua de (3) do invariante, podemos descartar o second_largest
      // anterior e substituir pelo largest anterior.
      second_largest = largest;
      // O maior encontrado agora é v[i]
      largest = v[i];
    } else if (second_largest < v[i]) {
      // Se v[i] <= largest && v[i] > second_largest, v[i] é o segundo.
      // Novamente, (3) do invariante permite descartar second_largest anterior.
      second_largest = v[i];
    }
    // Agora as três condições do invariante valem para 0 <= j <= i, e
    // portanto podemos incrementar i.
  }
  // Pós-condição: Junção das seguintes condições:
  // - largest >= second_largest
  // - Qualquer v[j], v[j] <= largest
  // - Qualquer v[j], v[j] <= second_largest || v[j] == largest
  // Esta condição é garantida pelo invariante junto com a condição de saída
  // do loop (que sai quando i == v.size())
  return {largest, second_largest};
}

// Um tipo artificial que guarda um valor de score junto com o nome de quem
// conseguiu esse escore.
// Como queremos selecionar os maiores scores em um vetor de Score, precisamos
// definir o operador usado na função two_largest, que é o operador <.
// Também precisamos de construtores devido à forma como o tipo é usado:
// - Contrutor default para a criação das variáveis largest e second_largest
// - Construtor com o valor do score e nome para o código de inserção no vetor.
struct Score {
  double value;
  std::string name;
  Score() = default;
  Score(double v, std::string s) : value(v), name(s) {}
  // Ao comparar dois objetos Score, nos preocupamos apenas com o valor do score
  // e não com o nome.
  friend bool operator<(Score const &a, Score const &b) {
    return a.value < b.value;
  }
};

// Um programa de demonstração.
int main(int, char const *[]) {
  // Criamos um vetor de int.
  std::vector<int> some{3, 7, -4, 8, 5, 0, 2};
  // E um vetor de double.
  std::vector<double> some_doubles{3., 7., -4., 8., 5., 0., 2.};

  // Ao chamarmos two_largest no vetor de int, uma função com o código de
  // two_largest substituindo todos os lugares onde tem Value por int é criada.
  auto res = two_largest(some);
  std::cout << "Maior: " << res[0] << ", "
            << "segundo: " << res[1] << std::endl;

  // Quando chamamos com um vetor de double, os Value são substituidos por
  // double.
  auto res_double = two_largest(some_doubles);
  std::cout << "Maior: " << res_double[0] << ", "
            << "segundo: " << res_double[1] << std::endl;

  // Se chamamos em um vetor de Score, os Value são substituidos por Score.
  std::vector<Score> some_scores;
  some_scores.emplace_back(3, "a");
  some_scores.emplace_back(2, "b");
  some_scores.emplace_back(7, "c");
  some_scores.emplace_back(1, "d");

  auto res_scores = two_largest(some_scores);
  std::cout << "O maior score e: " << res_scores[0].value << " conseguido por "
            << res_scores[0].name << std::endl;
  std::cout << "O segundo maior score e: " << res_scores[1].value
            << " conseguido por " << res_scores[1].name << std::endl;
}