Seminar7

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

// 4 92 5 3 48 1 34
// 4 5 3 1 34 92 48
// 1 4 5 3 34 92 48
// 1 3 4 5 34 92 48
// 1 3 4 5 34 92 48

// 0: 1
// 1: 3
// 3: 5
// 4: 34
// 6: 92

// 1 2 3 5 6 4
//     j i
// Возвращает позицию опорного элемента после разбиения.
int Partition(std::vector<double>& v, int l, int r) {
    int i = l;
    int j = r - 2;
    while (i <= j) {
        for (; i < r && v[i] <= v[r - 1]; ++i);
        for (; j >= 0 && v[j] >= v[r - 1]; --j);
        if (i < j) std::swap(v[i], v[j]);
    }
    std::swap(v[i], v[r - 1]);
    return i;
}

double KStat(std::vector<double>& v, int k) {
    if (k > v.size()) {
        throw std::out_of_range("Запросили несуществующую статистику");
    }
    // l – включительно, r – не включается в рассмотрение.
    int l = 0;
    int r = v.size();
    while (true) {
        int pivot_pos = Partition(v, l, r);
        if (pivot_pos == k) {
            return v[k];
        }
        if (pivot_pos < k) {
            l = pivot_pos + 1;
        } else {
            r = pivot_pos;
        }
    }
}

int main() {
    std::vector<double> v{4, 92, 5, 3, 48, 1, 34};
    int k = 0;
    std::cin >> k;
    std::cout << KStat(v, k);
    return 0;
}

// Функция сравнения строк.
// a < z
// ab < z
// a < ab
bool CompareStrings(const std::string& str1, const std::string& str2) {
    const size_t min_length = std::min(str1.length(), str2.length());

    for (int i = 0; i < min_length; ++i) {
        if (str1[i] < str2[i]) return true;
        if (str1[i] > str2[i]) return false;
    }
    return min_length != str2.length();
}

long long x = 1;

int main1() {
    std::cout << "=================" << std::endl;
    for (char i = 1; i < 127; ++i) {
        std::cout << i;
        if (i % 32 == 0) std::cout << std::endl;
    }
    std::cout << "=================" << std::endl;

    std::string s1, s2;
    std::cin >> s1 >> s2;
    std::cout << (CompareStrings(s1, s2) ? "True" : "False") << std::endl;
    return 0;
}