Cod sursa(job #1018592)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 29 octombrie 2013 19:55:05
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;

ifstream cin("sdo.in");
ofstream cout("sdot.out");

int n, v[500000], k;

void swap( int &a, int &b ) {
    int aux = a;
    a = b;
    b = aux;
}
  
void qsort( int left, int right ) {
    if ( left >= right )
        return;
  
    int piv = v[left + rand() % ( right - left + 1 )], begin = left, end = right;
  
    while ( begin <= end ) {
        while ( v[begin] < piv )
            ++begin;
        while ( v[end] > piv )
            --end;
  
        if ( begin <= end ) {
            swap( v[begin], v[end] );
            ++begin;
            --end;
        }
    }
  
    if (k <= end)
      qsort( left, end );
    else
      qsort( begin, right );
}
  

int main()
{    
  srand(time(NULL));

  cin >> n >> k;

  for(int i = 0; i < n; i++)
    cin >> v[i];

  qsort(0, n - 1);

  cout << v[k - 1] << "\n";
    
  cin.close();
  cout.close();

  return 0;
}