Mai intai trebuie sa te autentifici.

Cod sursa(job #662071)

Utilizator rootsroots1 roots Data 15 ianuarie 2012 19:37:42
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <stdlib.h>
#include <time.h>

#define vL 3000001

using namespace std;

ifstream in;
ofstream out;

int v[vL];

inline int quicksort(int L,int R)
{
    int piv=v[L+(rand()%(R-L+1))],i,j;

    for(i=L-1,j=R+1;1;)
    {
        do ++i;
        while(v[i]<piv);

        do --j;
        while(piv<v[j]);

        if(i<j)
        {
            v[i]^=v[j];
            v[j]^=v[i];
            v[i]^=v[j];
        }
        else return j;
    }

    return 0;
}

inline void kmin(int L,int R,int K)
{
    if(L==R) return;

    int M=quicksort(L,R);
    int len=M-L+1;

    if(K<=len) kmin(L,M,K);
    else kmin(M+1,R,K-len);
}

int main()
{
    int N,K;

    in.open("sdo.in");

    in>>N>>K;
    for(int i=1;i<=N;++i) in>>v[i];

    in.close();

    srand(time(NULL));
    kmin(1,N,K);

    out.open("sdo.out");

    out<<v[K]<<'\n';

    out.close();

    return 0;
}