Cod sursa(job #2986074)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 27 februarie 2023 18:03:40
Problema Statistici de ordine Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int partition(vector<int>& v, int left, int right) {
  int nextPz = left;
  int pivot = v[right];

  for (int i = left; i <= right; ++i)
    if (v[i] <= pivot) {
      swap(v[nextPz], v[i]);
      ++nextPz;
    }

  return nextPz - 1;
}
  
int nthElement(vector<int>& v, int left, int right, int position) {
  int pivotPos = partition(v, left, right);
  if (pivotPos == position)
    return v[pivotPos];

  if (pivotPos > position)
    return nthElement(v, left, pivotPos - 1, position);

  return nthElement(v, pivotPos + 1, right, position); 
}

int main() {

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

  int N, K;

  scanf("%d%d", &N, &K);
  --K;
  
  vector<int> v(N);
  for (int i = 0; i < N; ++i)
    scanf("%d", &v[i]);

  printf("%d\n", nthElement(v, 0, (int)v.size() - 1, K));
  
  
  return 0;
}