Cod sursa(job #663604)

Utilizator mr.johnFMI - Laceanu Ionut-Adrian mr.john Data 18 ianuarie 2012 19:16:24
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <algorithm>

using namespace std;

int h[3000004]; 
  ifstream fin("sdo.in");
  ofstream fout("sdo.out");

void nth(int start,int stop,int k){
  if (start==stop) return;
  int i=start-1,j=stop+1;
  int pivot=h[start + rand()%(stop-start+1)];
  while(i<j){
    while(h[++i]<pivot);
    while(h[--j]>pivot);
    if (i<j) swap(h[i],h[j]);
  }
  int t=j-start+1;
  if (t>=k)
    nth(start,j,k);
  else
    nth(j+1,stop,k-t);
}

int main(){
  int n,k;
  fin>>n>>k;
  for (int i=1; i<=n;i++){
    fin>>h[i];
  }
  nth(1,n,k);
  fout<<h[k];
  return 0;
}