Cod sursa(job #1323092)

Utilizator tweetyMarinescu Ion tweety Data 20 ianuarie 2015 17:27:34
Problema Statistici de ordine Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <algorithm>
#include <ctime>
using namespace std;

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

int N;
int k;
int* v;

void SDO(int* a, int start, int end, int kth)
{
    if (start > end)
        return;

    int i = start;
    int j = end;
    int pivot = a[(start + end) / 2]; //a[rand() % (end - start + 1) + start];

    while (i <= j)
    {
        while (a[i] < pivot)
            ++i;

        while (a[j] > pivot)
            --j;

        if (i <= j)
            swap (a[i++], a[j--]);
    }

    if (end - start == 1 || end == start)
    {
        if (start == kth)
            out << a[start];
        else
            out << a[end];
    }
    else
    {
        if (kth <= j)
            SDO(a, start, j, kth);
        else
            SDO(a, i, end, kth);
    }
}

int main()
{
    in >> N >> k;
    v = new int[N + 1];

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

    srand(time(NULL));
    SDO(v, 1, N, k);

    in.close();
    out.close();
    delete[] v;

    return 0;
}