Cod sursa(job #2830250)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 9 ianuarie 2022 17:47:20
Problema Statistici de ordine Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, K;
vector<int> v;

/// gasim pivotul
int pivot(int st, int dr)
{
    int i=st, j=dr, d=0;
    while(i<j){
        if(v[i]>v[j]){
            swap(v[i],v[j]);
            d=1-d;
        }
        i+=d;
        j-=1-d;
    }
    return i;
}

int quickSelect(int st, int dr, int nr)
{
    int poz=pivot(st,dr);
    if(poz-st+1==nr)
        return v[poz];
    if(poz-st+1>nr)
        return quickSelect(st,poz-1,nr);
    return quickSelect(poz+1,dr,nr-(poz-st+1));
}

int main()
{
    fin>>N>>K;
    int x;
    for(int i=0;i<N;i++){
        fin>>x;
        v.push_back(x);
    }
    fout<<quickSelect(0,N-1,K);

    fin.close();
    fout.close();
    return 0;
}