#include <algorithm>
#include <fmt/core.h>

// Zaimplementuj algorytm, który pobiera zakres niepowtarzalnych elementów oraz
// wartość. Algorytm zwraca liczbę elementów, które są
// większe od mediany* zakresu i jednocześnie mniejszych niż podana wartość.

// Algorytm ma działać dla dowolnych typów, które obsługują wymagane operacje i
// ma być optymalny wydajnościowo. Można założyć, że otrzymany zakres pozwala na
// wielokrotną iterację po elementach oraz swobodne skakanie z dowolnego
// elementu na dowolny inny (innymi słowy modeluje random_access_range).
// Dozwolona jest modyfikacja kolejności elementów otrzymanego zakresu.
//
// *mediana - wartość środkowa zakresu

// rozwiązanie:

using namespace std;

auto process(auto from, auto to, auto value) {
    if (from == to) {
        return 0l;
    }
    auto middle = from + (to - from) / 2;
    nth_element(from, middle, to);
    return count_if(middle + 1, to, [&](auto v) { return v < value; });
}

#include <catch2/catch_test_macros.hpp>

#include <array>
#include <string>

TEST_CASE("empty range") {
    array<int,1> tab = {1};
    REQUIRE(process(tab.begin(), tab.begin(), 2) == 0);
}

TEST_CASE("ints, all smaller, value=20, counted={1, 4, 7, 9}") {
    array tab = {14, 9, 7, 4, 1};
    REQUIRE(process(tab.begin(), tab.end(), 20) == 4);
}

TEST_CASE("doubles, all smaller, value=6, counted={1.0, 2.4}") {
    array tab = {1.0, 2.4, 3.6, 4.8};
    REQUIRE(process(tab.begin(), tab.end(), 6) == 2);
}

TEST_CASE("ints, median=70, value=95, counted={90}") {
    array tab = {10, 70, 90, 40, 140}; // median = 70
    REQUIRE(process(tab.begin(), tab.end(), 95) == 1);
}