Mai intai trebuie sa te autentifici.
Cod sursa(job #2619524)
Utilizator | Data | 27 mai 2020 21:12:23 | |
---|---|---|---|
Problema | Statistici de ordine | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.12 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sdo.in");
ofstream fout("sdo.out");
int mediana3(int st, int dr, int mij, vector < long long > & v) {
int s = v[st], m = v[mij], d = v[dr];
if ((s > m) != (s > d))
return st;
else if ((m > s) != (m > dr))
return mij;
else
return dr;
}
int partitie(int st, int dr, vector < long long > & v) {
int piv = v[dr], i;
int indexmin = st;
for (i = st; i < dr; i++) {
if (v[i] <= piv) {
swap(v[i], v[indexmin]);
indexmin++;
}
}
swap(v[dr], v[indexmin]);
return indexmin;
}
void QuickSortMed3(int st, int dr, vector < long long > & v) {
if (st < dr) {
int mij = (st + dr) / 2;
int piv = mediana3(st, dr, mij, v);
swap(v[piv], v[dr]);
piv = partitie(st, dr, v);
QuickSortMed3(st, piv - 1, v);
QuickSortMed3(piv + 1, dr, v);
}
}
int main()
{
vector<long long> v;
int n,k,x;
fin>>n>>k;
for(int i=0;i<n;i++)
{
fin>>x;
v.push_back(x);
}
QuickSortMed3(0, v.size() - 1, v);
int ct=0;
fout<<v.at(k-1);
return 0;
}