Cod sursa(job #1972490)

Utilizator GoogalAbabei Daniel Googal Data 23 aprilie 2017 11:41:44
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <ctime>
#include <fstream>
#include <cstdlib>

using namespace std;

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

int const nmax = 3000000;

int v[1 + nmax], n, k;

int kthelement(int a, int b, int k) {
  if(a < b) {
  int ipivot = a + rand() % (b - a + 1);
  int pivot = v[ipivot];

  int i = a - 1;
  int j = a;
  while(j <= b){
    if(v[j] <= pivot) {
      i++;
      swap(v[i], v[j]);
    }
    j++;
  }
  if(k <= i - a + 1)
    return kthelement(a, i, k);
  else
    return kthelement(i + 1, b, k - (i - a + 1));
  } else
    return v[a];
}

int main() {
  srand(time(NULL));
  in >> n >> k;

  for(int i = 1; i <= n; i++)
    in >> v[i];
  in.close();

  out << kthelement(1, n, k);
  out.close();
  return 0;
}