Cod sursa(job #2384566)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 20 martie 2019 21:27:57
Problema Statistici de ordine Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>

#define NMAX 4000001

using namespace std;

int v [NMAX], k ;

void statisticideordine (int begin, int end, int v [NMAX], int k ) {
  int b, e, pivot ;
  b = begin, e = end, pivot = v [ ( begin + end ) / 2 ] ;
  while (b <= e ) {
    while (v[b] < pivot ) b++;
    while (v[e] > pivot ) e--;
    if (b <= e ) {
      swap (v[b], v[e]) ;
      b++;
      e--;
    }
  }
  if (e >= k )
    statisticideordine(begin, e, v, k ) ;
  else {
    if (k >= b )
      statisticideordine(b, end, v, k ) ;
    else
      return ;
  }
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("sdo.in", "r" ) ;
  fout = fopen ("sdo.out", "w" ) ;
  int n, i ;
  fscanf (fin, "%d%d", &n, &k ) ;
  for (i = 1 ; i <= n ; i++ )
    fscanf (fin, "%d", &v[i] ) ;
  statisticideordine(1, n, v, k ) ;
  fprintf (fout, "%d", v[k] ) ;
  return 0;
}