Cod sursa(job #3372535)

Utilizator rapidu36Victor Manz rapidu36 Data 4 noiembrie 2026 09:59:25
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#include <cstdlib>

using namespace std;

void part_3(vector <int> &v, int st, int dr, int &p1, int &p2) {
    int p_ini_p = rand() % (dr - st + 1) + st;
    swap(v[p_ini_p], v[dr]);
    int i = st;
    p1 = st;
    p2 = dr - 1;
    while (i <= p2) {
        if (v[i] < v[dr]) {
            swap(v[p1++], v[i++]);
        } else if (v[i] > v[dr]) {
            swap(v[p2--], v[i]);
        } else {
            i++;
        }
    }
    swap(v[++p2], v[dr]);
}

void qs(vector<int> &v, int st, int dr, int k) {
    if (st >= dr) {
        return;
    }
    int p1, p2;
    part_3(v, st, dr, p1, p2);
    if (k < p1) {
        qs(v, st, p1 - 1, k);
    }
    if (k > p2) {
        qs(v, p2 + 1, dr, k);
    }
}

int main() {
    ifstream fin("sdo.in");
    ofstream fout("sdo.out");
    int n, k;
    fin >> n >> k;
    k--;
    vector <int> v(n);
    for (int i = 0; i < n; i++) {
        fin >> v[i];
    }
    fin.close();
    qs(v, 0, n - 1, k);
    fout << v[k] << "\n";
    fout.close();
    return 0;
}