Cod sursa(job #2950137)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 3 decembrie 2022 00:18:10
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#define NMAX 3000000

using namespace std;

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


int v[NMAX];

int lomutoPartition(int lo, int hi) {
    int pivotIndex = lo + rand() % (hi - lo  + 1), tmp;
    tmp = v[lo], v[lo] = v[pivotIndex], v[pivotIndex] = tmp;

    int pivot = v[lo], curr = lo;

    for (int i = lo + 1; i <= hi; ++i) {
        if (v[i] < pivot) {
            ++curr;
            tmp = v[curr], v[curr] = v[i], v[i] = tmp;
        }
    }
    
    tmp = v[curr], v[curr] = v[lo], v[lo] = tmp;

    return curr;
}

int quickSelect(int k, int lo, int hi) {
    int partIndex = lomutoPartition(lo, hi);
    if (k == partIndex) {
        return v[k];
    } else if (k < partIndex) {
        return quickSelect(k, lo, partIndex - 1);
    } else {
        return quickSelect(k, partIndex + 1, hi);
    }   
}

int main()
{
    int n, k;
    fin >> n >> k;

    for (int i = 0; i < n; ++i) {
        fin >> v[i];
    }

    fout << quickSelect(k - 1, 0, n - 1);

    return 0;
}