Cod sursa(job #3372500)

Utilizator georgiemanea georege caharisitan georgie Data 4 noiembrie 2026 08:48:05
Problema Statistici de ordine Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("sdo.in");
ofstream fout("sdo.out");

int v[3000001], n, k;
int part(int ni, int nj)
{
    int i=ni-1, j=nj+1, p=v[ni+(rand()%(nj-ni+1))];
    while(true)
    {
        do
        {
            i++;
        }while(v[i]<p);
        
        do
        {
            j--;
        }while(p<v[j]);
        if(i<j)
            swap(v[i], v[j]);
        else
            return j;
    }
    return 0;
}
void sel(int ni, int nj, int k)
{
    if(ni==nj)
        return;
    int q=part(ni, nj);
    int t=q-ni+1;
    if(t>=k)
        sel(ni, q, k);
    else
        sel(q+1, nj, k-t);
}
int main()
{
    srand(time(NULL));
    fin >> n >> k;
    for(int i=1; i<=n; i++)
        cin >> v[i];
    sel(1, n, k);
    fout << v[k];
    return 0;
}