Cod sursa(job #1850953)
Utilizator | Ionescu Teodor teoionescu | Data | 19 ianuarie 2017 04:35:17 |
---|---|---|---|
Problema | Statistici de ordine | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include<fstream>
using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");
int n,k,v[3000001];
int part(int st, int dr){
int x=v[(st+dr)/2];
st--,dr++;
while(st<dr){
do{st++;}while(v[st]<x);
do{dr--;}while(v[dr]>x);
if(st<dr) swap(v[st],v[dr]);
}
return dr;
}
void calc(int st, int dr, int k){
if (st < dr){
int j = part(st, dr);
if (k <= j-st+1) calc(st,j,k);
else calc(j+1,dr,k-(j-st+1));
}
}
int main(){
in>>n>>k;
for(int i=1;i<=n;i++) in>>v[i];
calc(1, n, k);
out<<v[k];
return 0;
}