Cod sursa(job #2722898)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 13 martie 2021 13:00:20
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <cstdlib>

const int MAXN = 3e6 + 1;

using namespace std;

ifstream in("sdo.in");
ofstream out("sdo.out");

int n,k,v[MAXN],a[MAXN];

int quick_sort(int left = 1,int right = n){
    int pivot = left + rand() % (right - left + 1);
    int index = left - 1;
    int poz1,poz2;
    for(int i = left; i <= right; i++)
        if(v[i] < v[pivot])
            a[++index] = v[i];
    poz1 = index + 1;
    for(int i = left; i <= right; i++)
        if(v[i] == v[pivot])
            a[++index] = v[i];
    poz2 = index;
    for(int i = left; i <= right; i++)
        if(v[i] > v[pivot])
            a[++index] = v[i];
    for(int i = left; i <= right; i++)
        v[i] = a[i];
    /// < < < =    = = = > > > >
    ///       poz1  poz2
    if(poz1 <= k && k <= poz2)
        return v[poz1];
    if(k < poz1)
        return quick_sort(left,poz1 - 1);
    if(k > poz2)
        return quick_sort(poz2 + 1,right);
}

int main()
{

    in>>n>>k;
    for(int i = 1; i <= n; i++)
        in>>v[i];
    out<<quick_sort();
    return 0;
}