Cod sursa(job #1018598)

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

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

int n, v[3000000], 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 = 1; i <= n; i++)
    cin >> v[i];

  qsort(1, n);

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

  return 0;
}