Cod sursa(job #2374707)

Utilizator GoogalAbabei Daniel Googal Data 7 martie 2019 20:04:21
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

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

int const NMAX = 3 * 1e6;

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

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];


  out << kthelement(1, n, k);

  in.close();
  out.close();

  return 0;
}