Cod sursa(job #1838770)

Utilizator BLz0rDospra Cristian BLz0r Data 1 ianuarie 2017 19:05:53
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

#define NMAX 3000002

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

int v[NMAX];

void kth_element(int left, int right, int k) {

    if (left >= right)
        return;

    int i = left, j = right;
    int pivot = v[left + rand() % (right - left + 1)];

    do {

        while (v[i] < pivot) i++;
        while (v[j] > pivot) j--;

        if (i <= j) {

            swap(v[i], v[j]);

            i++;
            j--;
        }

    }while (i < j);

    if (i <= k && k <= right)
        kth_element(i, right, k);

    if (left <= k && k <= j)
        kth_element(left, j, k);
}

int main() {

    srand(time(nullptr));

    int N, K;
    fin >> N >> K;

    for (int i = 1; i <= N; ++i)
        fin >> v[i];

    kth_element(1, N, K);

    fout << v[K];

    return 0;
}