Cod sursa(job #1697336)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 1 mai 2016 17:41:00
Problema Statistici de ordine Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>

using namespace std;

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

    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 + 1 < (j - left + 1))
        processKth(left, j, arr, k);
    else if (i < right && k + 1 > (j - left + 1))
        processKth(i, right, arr, (k + 1) - (j - left + 1) - 1);
}

int main()
{
    int n, i, k;
    ifstream f("sdo.in");
    ofstream g("sdo.out");
    f >> n >> k;
    k--;
    int arr[n];
    for (i = 0; i < n; i++)
        f >> arr[i];
    processKth(0, n - 1, arr, k);
    g << arr[k];
    f.close();
    g.close();
    return 0;
}