Cod sursa(job #1474489)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 22 august 2015 02:15:02
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int a[3000006],n,k;
int part(int s,int e)
{
    int p=a[s],i=s-1,j=e+1;
    while(1)
    {
        do
        {
            i++;
        }while(a[i]<p&&i<=e);
        do
        {
            j--;
        }while(a[j]>p&&j>=s);
        if(i<j) swap(a[i],a[j]);
        else return j;
    }
    return 0;
}
void sdo(int s,int e,int k)
{
    if(s>=e) return;
    int p=part(s,e),p2;
    p2=p-s+1;
    if(p2>=k) sdo(s,p,k);
    else sdo(p+1,e,k-p2);
}
int main()
{
    freopen ("sdo.in","r",stdin);
    freopen ("sdo.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sdo(1,n,k);
    printf("%d\n",a[k]);
}