Cod sursa(job #2611611)

Utilizator buhaidarius@gmail.comBuhai Darius [email protected] Data 7 mai 2020 10:50:08
Problema Statistici de ordine Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<int> v;

int partition(int l, int r){
    int x = v[r], i = l;
    while(l<r){
        if(v[l]<=x)
            swap(v[i++], v[l]);
        l++;
    }
    swap(v[i], v[r]);
    return i;
}

int quickSearch(int l, int r, int k){
    if(l>r) return 0;
    int m = partition(l, r);
    if(m-l==k-1)
        return v[m];
    if(m-l>k-1)
        return quickSearch(l, m-1, k);
    return quickSearch(m+1, r, k-m+l-1);
}

int main() {
    ifstream fin("sdo.in");
    ofstream fout("sdo.out");

    int n, k, x;
    fin>>n>>k;
    for(int i=0;i<n;i++){
        fin>>x;
        v.emplace_back(x);
    }
    fout<<quickSearch(0, n-1, k);
    return 0;
}