Cod sursa(job #1972493)

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

using namespace std;

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

int const DIM = 1000000;
int const nmax = 3000000;

int v[1 + nmax], n, k, poz;
char buff[DIM];

int read(){
  int x = 0;

  while(!isdigit(buff[poz]))
    if(++poz == DIM)
      in.read(buff,DIM), poz = 0;

  while(isdigit(buff[poz])){
    x = x * 10 + (buff[poz] - '0');

    if(++poz == DIM)
      in.read(buff,DIM), poz = 0;
  }

  return x;
}

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));
  n = read();
  k = read();

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

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