Cod sursa(job #1024019)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 8 noiembrie 2013 00:20:19
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

void swap(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}

int partition(vector<int> &v, const int &left, const int &right) {
  int i = left - 1, j = right + 1, piv = v[left + rand()%(right - left + 1)];
  while (1) {
    do {
      ++i;
    } while (v[i] < piv);
    do {
      --j;
    } while (v[j] > piv);
    if (i < j) {
      swap(v[i], v[j]);
    } else {
      return j;
    }
  }
  return 0;
}

vector<int> &quickSelect(vector<int> &v, const int &left, const int &right, const int &k) {
  if (left == right) {
    return v;
  }
  int piv = partition(v, left, right);
  int dist = piv - left + 1;
  if (dist >= k) {
    return quickSelect(v, left, piv, k);
  } else {
    return quickSelect(v, piv + 1, right, k - dist);
  }
}

int main() {
  int N, K;
  vector<int> v;
  v.push_back(1337);

  ifstream in("sdo.in");
  in >> N >> K;
  for (int i = 0; i < N; ++i) {
    int val;
    in >> val;
    v.push_back(val);
  }
  in.close();

  v = quickSelect(v, 1, N, K);

  ofstream out("sdo.out");
  out << v[K];
  out.close();

  return 0;
}