Cod sursa(job #2132463)

Utilizator arabtrappinTudor Bursuc arabtrappin Data 15 februarie 2018 19:47:07
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#define DMAX 3000001
using namespace std;
int v[DMAX];
int n,k;
ifstream fin("sdo.in");
ofstream fout("sdo.out");
int divi(int st,int dr)
{
 int piv;
 piv=v[st];
 while (st<dr)
    {//liber la stanga
     while (st<dr && v[dr]>=piv)dr--;
     v[st]=v[dr];
     //liber la dreapta
     while(st<dr && v[st]<=piv)st++;
     v[dr]=v[st];
    }

 v[st]=piv;

 return st;
}
int ksmallest(int st,int dr,int k)
{
    int piv;
    piv=divi(st,dr);
    if(k<piv-st+1)return ksmallest(st,piv,k);
    else if(k>piv-st+1)return ksmallest(piv+1,dr,k-piv);
    else return v[piv];
}
int main()
{int i;
 fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fout<<ksmallest(1,n,k);
    return 0;
}