Cod sursa(job #1850769)

Utilizator NarniussAnghelache Bogdan Narniuss Data 18 ianuarie 2017 21:49:00
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define NMAX 3000002

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

int v[NMAX];

void k_elem(int left, int right, int k)
{
  int i, j;
  if(left >= right){
    return;
  }

   i = left; j = right;
  int pivot = v[left + rand() % (right - left + 1)];

  do{

    while(v[i] < pivot) i++;
    while(v[j] > pivot) j--;

    if(i <= j){
      swap(v[i], v[j]);
      i++;
      j--;
    }
    }while(i < j);

    if(i <= k && k <= right)
      k_elem(i, right, k);
    if(left <= k && k <= j)
      k_elem(left,j, k);
}

int main() {
int n, k, i;
  time_t t;
  srand((unsigned) time(&t));

  fin>>n>>k;


  for(i = 1 ; i <= n ; i++)
    fin>>v[i];

  k_elem(1, n, k);
  fout << v[k];

  return 0;
}