Cod sursa(job #659114)

Utilizator danieladDianu Daniela danielad Data 10 ianuarie 2012 01:36:27
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include<cstdlib>
#define MAXN 3000002

using namespace std;

ifstream f("sdo.in");
ofstream g("sdo.out");

int v[MAXN],n,k;
int part(int left,int right)
{
    int i=left-1,j=right+1,val=v[left +rand()%(right-left+1)];
    while(1)
    {   do
		i++;
	    while(v[i]<val);
			
        do j--;
        while(v[j]>val);
			
		
         if(i<j)
            swap(v[i],v[j]);
         else
         return j;
    }
}
void quick(int left,int right,int k)
{
    if(left==right) return;
    int m=part(left,right);
    int x;
    x=m-left+1;
    if(x>=k) quick(left,m,k);
    else quick(m+1,right,k-x);
}

int main()
{
    f>>n>>k;
    for(int i=1;i<=n;i++)
        f>>v[i];
     quick(1,n,k);
     g<<v[k]<<"\n";
    return 0;
}