Cod sursa(job #1766064)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 27 septembrie 2016 13:20:40
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;

void orderStatistic(int left, int right, int k, int arr[])
{
    int i = left, j = right;
    int pivot = arr[left + (right - left) / 2];

    while (i <= j)
    {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j)
        {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }

    if (left < j && k >= left && k <= j)
        orderStatistic(left, j, k, arr);
    if (i < right && k >= i && k <= right)
        orderStatistic(i, right, k, arr);
}

int main()
{
    int N, k;
    ifstream f("sdo.in");
    f >> N >> k;
    int arr[N];
    for (int i = 0; i < N; i++)
        f >> arr[i];
    f.close();

    orderStatistic(0, N - 1, k - 1, arr);

    ofstream g("sdo.out");
    g << arr[k - 1];
    g.close();

    return 0;
}