Cod sursa(job #1850953)

Utilizator teoionescuIonescu Teodor teoionescu Data 19 ianuarie 2017 04:35:17
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<fstream>
using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");
int n,k,v[3000001];

int part(int st, int dr){
    int x=v[(st+dr)/2];
    st--,dr++;
    while(st<dr){
        do{st++;}while(v[st]<x);
        do{dr--;}while(v[dr]>x);
        if(st<dr) swap(v[st],v[dr]);
    }
    return dr;
}

void calc(int st, int dr, int k){
    if (st < dr){
        int j = part(st, dr);
        if (k <= j-st+1) calc(st,j,k);
        else calc(j+1,dr,k-(j-st+1));
    }
}

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