Cod sursa(job #2187303)

Utilizator NeredesinI am not real Neredesin Data 26 martie 2018 13:14:36
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 = 3 * 1e6;

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

int kth_el(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 kth_el(a, i, k);
  else
    return kth_el(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];

  out << kth_el(1, n, k) << '\n';

  in.close();
  out.close();
  return 0;
}