Cod sursa(job #2669881)

Utilizator TghicaGhica Tudor Tghica Data 8 noiembrie 2020 12:49:27
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

int v[3000000];

void nth_elem( int bo, int eo, int k ) {
  int b = bo, e = eo, pivot = v[(bo + eo) / 2];
  while ( v[b] < pivot )
    b++;
  while ( v[e] > pivot )
    e--;
  while ( b < e ) {
    swap( v[b], v[e] );
    do
      b++;
    while ( v[b] < pivot );

    do
      e--;
    while ( v[e] > pivot );
  }
  if ( bo < e && k <= e )
    nth_elem( bo, e, k );
  else if ( e + 1 < eo )
    nth_elem( e + 1, eo, k );
}

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