Cod sursa(job #3237860)

Utilizator tsg38Tsg Tsg tsg38 Data 13 iulie 2024 19:35:40
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

const int DIM = 3e6;

int v[DIM];

void quicksort( int l, int r ) {
  int p = v[l + rng() % (r - l + 1)];
  int st = l, dr = r;

  while ( v[st] < p ) ++st;
  while ( v[dr] > p ) --dr;

  while ( st < dr ) { 
    swap(v[st], v[dr]);

    while ( v[++st] < p );
    while ( v[--dr] > p );
  }

  if ( l < dr ) quicksort(l, dr);
  if ( dr + 1 < r ) quicksort(dr + 1, r);
}

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int n, k;

  fin >> n >> k;
  for ( int i = 0; i < n; ++i ) {
	fin >> v[i];
  }
  quicksort(0, n - 1);
  fout << v[k - 1];
  fin.close();
  fout.close();
  return 0;
}