Cod sursa(job #1492347)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 27 septembrie 2015 16:44:32
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int partition(vector<int> &nums, int left, int right){

  int el = nums[left];
       
  int i = left+1, j = right;
       
  while(i <= j){
    if (nums[i] <= el) i++;
    if (nums[j] > el) j--;
    if (i < j){
      swap(nums[i], nums[j]);
    }
  }
  swap(nums[left], nums[j]);
       
  return j;
}

int main(){

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

  cin >> n >> k;
  std::vector<int> nums(n);

  for (int i = 0; i < n; i++){
    cin >> nums[i];
  }

  if (nums.size() == 0) return 0;

  int left = 0, right = nums.size()-1, idx;

  k--;
  do {
    idx = partition(nums, left, right);
            
    if (idx < k)
      left = idx + 1;
    else
      right = idx - 1;
            
  }while(idx != k);
        
  cout <<  nums[idx];
  
  return 0;
}