Cod sursa(job #2909837)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 16 iunie 2022 09:53:35
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>

std::ifstream cin("sdo.in");
std::ofstream cout("sdo.out");

int select(std::vector<int> &v, int l, int r, int stat) {
    if (r - l + 1 == 1) {
        return v[l];
    }

    int piv = v[l + rand() % (r - l + 1)];
    int rg = r;

    for (int i = l; i <= r;) {
        if (v[i] >= piv) {
            std::swap(v[i], v[rg]);
            rg--;
        } else {
            i++;
        }

        if (i > rg) {
            break;
        }
    }

    if (rg - l + 1 == stat) {
        return piv;
    }

    if (rg - l + 1 > stat) {
        return select(v, l, rg, stat);
    }

    return select(v, rg + 1, r, stat - (rg - l + 1));
}

int main() {
    int n, k;
    cin >> n >> k;

    std::vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    cout << select(v, 0, n - 1, k - 1);
    return 0;
}