Cod sursa(job #1704312)

Utilizator TincaMateiTinca Matei TincaMatei Data 18 mai 2016 16:30:33
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>

const int MAX_N = 3000000;

int v[MAX_N];

int kthelement(int st, int dr, int k) {
  int b, e, pivot, aux;
  b = st;
  e = dr;
  pivot = v[(b + e) / 2];
  while(b <= e) {
    while(v[b] < pivot) b++;
    while(v[e] > pivot) e--;
    if(b <= e) {
      aux = v[b];
      v[b] = v[e];
      v[e] = aux;
      b++;
      e--;
    }
  }
  if(st <= k && k <= e)
    return kthelement(st, e, k);
  else if(b <= k && k <= dr)
    return kthelement(b, dr, k);
  else
    return v[k];
}

int main() {
  int n, k, i;
  //nu folosesc freopen des,dar cand il folosesc sunt pe telefon
  freopen("sdo.in", "r", stdin);
  freopen("sdo.out", "w", stdout);
  scanf("%d%d", &n, &k);
  for(i = 0; i < n; i++)
    scanf("%d", &v[i]);
  printf("%d", kthelement(0, n - 1, k - 1));
}