Cod sursa(job #1480076)

Utilizator salam1Florin Salam salam1 Data 2 septembrie 2015 00:58:29
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int NMAX = 3000505;
int n, k, A[NMAX];

void read() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++)
    scanf("%d", &A[i]);
}

int get(int l, int r, int k) {
  if (l == r) {
    return A[l];
  }

  int pos = rand() % (r - l + 1) + l;
  swap(A[r], A[pos]);
  pos = r;

  int smt = 0;
  for (int i = l; i < r; i++) {
    if (A[i] < A[pos]) {
      swap(A[i], A[l + smt]);
      smt++;
    }
  }
  swap(A[pos], A[l + smt]);
  smt++;

  if (smt >= k) {
    return get(l, l + smt - 1, k);
  }
  return get(l + smt, r, k - smt);
}

int main() {
  freopen("sdo.in", "r", stdin);
  freopen("sdo.out", "w", stdout);

  read();
  srand(time(0));
  printf("%d\n", get(1, n, k));
  return 0;
}