Pagini recente » Cod sursa (job #2654207) | Diferente pentru suffix-array-liniar intre reviziile 54 si 55 | Cod sursa (job #609323)
Cod sursa(job #609323)
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
int a[3000010],n,i,k;
int part(int st, int sf) {
int i=st,j=sf,p=a[st+(rand()%(sf-st+1))],aux;
while (1) {
while (a[i]<p) i++;
while (a[j]>p) j--;
if (i<j) {
aux=a[i];a[i]=a[j];a[j]=aux;
}
else return j;
}
return 0;
}
void alg_sdo(int st,int sf,int k) {
if (st==sf) return;
int q=part(st,sf);
int t=q-st+1;
if (t>=k) alg_sdo(st,q,k);
else alg_sdo(q+1,sf,k-t);
}
int main() {
srand(time(NULL));
f >> n >> k;
for (i=1;i<=n;i++) f >> a[i];
alg_sdo(1,n,k);
g << a[k] << '\n';
f.close();g.close();
return 0;
}