Cod sursa(job #3200411)

Utilizator abelesefBurduhos Abel abelesef Data 4 februarie 2024 16:42:26
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("sdo.in");
ofstream fout("sdo.out");
int n,k,a[3000002];

int partition(int l,int h) {
        int i = l,j = h;
        swap(a[l],a[(l+h)/2]);
        while(i<j) {
                do {
                        i++;
                } while(a[i]<=a[l]);
                do {
                        --j;
                } while(a[j]>a[l]);
                if (i<j)
                        swap(a[i],a[j]);
        }
        swap(a[l],a[j]);
        return j;
}

int QuickSelect(int l,int h) {
        if (l==h)
                return a[l];
        int q = partition(l,h);
        if (q == k) return a[q];
        if (q > k)
                return QuickSelect(l,q);
        else
                return QuickSelect(q+1,h);
}

int main() {
        fin>>n>>k;
        for (int i = 1;i<=n;++i)
                fin>>a[i];
        a[n+1] = INT_MAX;
        fout<<QuickSelect(1,n+1);
        return 0;
}