Cod sursa(job #3125175)

Utilizator CosminDMRCosmin Damureanu CosminDMR Data 2 mai 2023 10:20:22
Problema Statistici de ordine Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream>
#define dim 3000001
using namespace std;
ifstream in ("sdo.in");
ofstream out("sdo.out");
unsigned int n, k, v[dim];
unsigned int pivot(int st, int dr)
{
    int dst = 0, ddr = 1;
    int mid = (st + dr) / 2;
    swap(v[st], v[mid]);
    while(st < dr) {
        if (v[st] > v[dr]) {
            swap(v[st], v[dr]);
            swap(dst, ddr);
        }
        st += dst;
        dr -= ddr;
    }
    return st;
}
unsigned int quickSelect(int st, int dr)
{
    if (st < dr) {
        int p = pivot(st, dr);
        if (p == k)
            return v[p];
        else if (k < p)
            quickSelect(st, p-1);
        else
            quickSelect(p+1, dr);
    }
}
int main()
{
    in >> n >> k;
    for (int i = 1; i <= n; i++)
        in >> v[i];
    out << quickSelect(1, n);
    return 0;
}