Cod sursa(job #1843971)

Utilizator stefanmereutaStefan Mereuta stefanmereuta Data 9 ianuarie 2017 16:44:37
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <time.h>
#include <algorithm>
#include <vector>

using namespace std;

void quicksort(vector<int> &v, int k, int st, int dr) {
    int pivot = v[rand() % (dr - st) + st];
    int i = st, j = dr, aux;

    do {
        while (v[i] < pivot && i < dr) {
            i++;
        }

        while (v[j] > pivot && j > st) {
            j--;
        }

        if (i <= j) {
            aux = v[i];
            v[i] = v[j];
            v[j] = aux;

            i++;
            j--;
        }
    } while (i <= j);

    if (st < j && k <= j) {
        quicksort(v, k, st, j);
    } else if (i < dr && k >= i) {
        quicksort(v, k, i, dr);
    }
}

int main()
{
    ifstream fin("sdo.in");
    ofstream fout("sdo.out");

    srand(clock());

    int n, k, x;
    vector<int> v;

    fin >> n >> k;

    k--;

    for (int i = 0; i < n; i++) {
        fin >> x;
        v.push_back(x);
    }

    quicksort(v, k, 0, n - 1);

    fout << v[k];

    fin.close();
    fout.close();

    return 0;
}