Cod sursa(job #935199)

Utilizator whoasdas dasdas who Data 2 aprilie 2013 00:24:24
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
/*
ID: i.adri1
PROG: sdo
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <assert.h>
#include <math.h>
#include <string.h>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

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

void sdo(int *v, int k, int l, int r)
{
    if (r - l < 1)
        return;

    int piv = rand() % (r-l+1) + l;
    swap(v[piv], v[r]);
    piv = v[r];
    int pfge = l;
    for (int i = l; i < r; i++)
        if (v[i] < piv) {
            swap(v[i], v[pfge]);
            pfge++;
        }
    swap(v[pfge], v[r]);

    if (pfge == k)
        return;
    if (pfge > k)
        sdo(v, k, l, pfge - 1);
    else
        sdo(v, k, pfge + 1, r);
}

int main()
{
    int n, k = 0;
    in>>n>>k;
    srand(n*k*773);
    int* v = new int[n];
    for (int i = 0; i < n; i++)
        in>>v[i];
    sdo(v, k - 1, 0, n-1);
    out<<v[k-1]<<endl;
    return 0;
}