Cod sursa(job #3183578)

Utilizator biancalautaruBianca Lautaru biancalautaru Data 12 decembrie 2023 12:49:57
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
#define DIM 3000001
using namespace std;
ifstream fin("sdo.in");
ofstream fout("sdo.out");
int n,k,v[DIM];

int pivot(int st,int dr) {
    swap(v[st],v[st+rand()%(dr-st+1)]);
    int di=0,dj=1;
    while (st<dr) {
        if (v[st]>v[dr]) {
            swap(v[st],v[dr]);
            swap(di,dj);
        }
        st+=di;
        dr-=dj;
    }
    return st;
}

int cauta(int st,int dr,int k) {
    if (st==dr)
        return v[st];
    int p=pivot(st,dr);
    if (p==k)
        return v[k];
    if (p>k)
        return cauta(st,p-1,k);
    return cauta(p+1,dr,k);
}

int main() {
    fin>>n>>k;
    for (int i=1;i<=n;i++)
        fin>>v[i];
    srand(time(0));
    fout<<cauta(1,n,k);
    return 0;
}