Cod sursa(job #2942901)

Utilizator andiRTanasescu Andrei-Rares andiR Data 20 noiembrie 2022 12:05:04
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>

#define Nmax 3000000
using namespace std;
ifstream fin ("sdo.in");
ofstream fout ("sdo.out");
int K,N;
unsigned int v[Nmax];

int Quick_Select(unsigned int v[], int begin, int end, int k){
    int b=begin, e=end;
  	long long pivot=v[(begin+end)/2];

    while (b<e){
        while (v[b]<pivot) b++;
        while (v[e]>pivot) e--;
    	if (b<=e){
     	    swap(v[b], v[e]);
      	    b++; e--;
        }
    }
    //cout<<begin<<' '<<end<<' '<<b<<' '<<e<<'\n';
    if (k<b && k>e){
        return v[k];
    }
    if (begin<e && k<=e) Quick_Select(v, begin, e, k);
    else if (b<end && b<=k) Quick_Select(v, b, end, k);
    return v[k];
}
int main()
{
    fin>>N>>K;
    K--;
    for (int i=0;i<N;i++)
        fin>>v[i];
    fout<<Quick_Select(v,0,N-1,K);
    return 0;
}