Cod sursa(job #2026754)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 24 septembrie 2017 23:35:14
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>

const int MAXN = 3e6;

int v[MAXN];

inline int kthelement(int l, int r, int k) {
  int aux, b = l, e = r, m = v[(l + r) >> 1];
  while (b <= e) {
    while (v[b] < m) ++b;
    while (v[e] > m) --e;
    if (b <= e) {
      aux = v[b];
      v[b] = v[e];
      v[e] = aux;
      ++b;
      --e;
    }
  }
  if (l <= k && k <= e) {
    kthelement(l, e, k);
  } else if (b <= k && k <= r) {
    kthelement(b, r, k);
  } else {
    return v[k];
  }
}

int main() {
  int n, k;
  FILE *f = fopen("sdo.in", "r");
  fscanf(f, "%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    fscanf(f, "%d", &v[i]);
  }
  fclose(f);
  f = fopen("sdo.out", "w");
  fprintf(f, "%d\n", kthelement(0, n - 1, k - 1));
  fclose(f);
  return 0;
}