Cod sursa(job #1256578)

Utilizator sherban26FMI Mateescu Serban-Corneliu sherban26 Data 6 noiembrie 2014 16:36:21
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#define NMAX 3000000

using namespace std;

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

unsigned long x[NMAX];

int part(unsigned long *v, int l, int r)
{
    int piv = v[(l + r) / 2];

    int i = l, j = r;

    while (1)
    {
        while (v[i] < piv)
            i++;
        while (v[j] > piv)
            j--;

        if (i < j)
        {
            swap(v[i], v[j]);
        }
        else
            return j;
    }

    return 0;
}

void statord(unsigned long *v, int l, int r, int k)
{
    if (l == r)
        return;

    int poz = part(v, l, r);
    int p = poz - l + 1;

    if (poz >= k)
        statord(v, l, poz, k);
    else
        statord(v, poz + 1, r, k);
}

int main()
{
    int n, k;

    f >> n >> k;

    for (int i = 0; i < n; i++)
        f >> x[i];

    statord(x, 0, n - 1, k - 1);

    g << x[k - 1];

    return 0;
}