Cod sursa(job #2758844)

Utilizator lahayonTester lahayon Data 13 iunie 2021 16:29:03
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>


using namespace std;

void qsort(vector<int>& A, int low, int high, int K){

    int i = low, j = high, pivot = A[low + rand() % (high - low + 1)];
    while(i <= j){
        while(A[i] < pivot) 
            ++i;
        while(A[j] > pivot)
            --j;
        if(i <= j){
            swap(A[i], A[j]);
            ++i;
            --j;
        }
    }
    int nr = j - low + 1;
    if(low < j && nr > K)
        qsort(A, low, j, K);
    else if(j + 1 < high)
        qsort(A, j + 1, high, K - nr);
}

int main()
{
    ifstream cin("sdo.in");
    ofstream cout("sdo.out");
         

    int N, K;
    cin >> N >> K;

    vector<int> A;

    for(int x; N > 0; --N){
        cin >> x;
        A.push_back(x);
    }
    qsort(A, 0, A.size()- 1, K);
    // nth_element(A.begin(), A.begin() + K - 1, A.end());

    cout << A[K - 1];

    cin.close();
    cout.close();

    return 0;
}