Cod sursa(job #1195551)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 7 iunie 2014 21:33:47
Problema Statistici de ordine Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
using namespace std;
#define MAX 3000001
int v[MAX], n, k;
int kthelem(int st, int dr);
int main()
{
	int i;
	freopen("sdo.in", "r", stdin);
	freopen("sdo.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for(i=1; i<=n; i++)
		scanf("%d", v+i);
	printf("%d", kthelem(1, n));
	
}
int kthelem(int st, int dr)
{
	int piv=v[(st+dr)/2], mici=st, mari=dr, i=st, j=dr, a, b;
	while(i<=j){
		while(i<=dr and v[i]<=piv){
			if(v[i]<piv) v[mici++]=v[i];
			i++;
		}
		while(j>=st and v[j]>=piv){
			if(v[j]>piv)  v[mari--]=v[j];
			j--;
		}
		if(i<j){
			a = v[i]; b = v[j];
			v[mici++]=b;
			v[mari--]=a;
			i++;
			j--;
		}
	}
	/*
	for(i=st; i<=dr; i++) printf("%d ", v[i]);
	printf("\n%d\n", piv);
	for(i=st; i<mici; i++) printf("%d ", v[i]);
	printf("!!");
	for(i=mari+1; i<=dr; i++) printf("%d ", v[i]);
	printf("\n");
	*/
	if(mici<=k and k<=mari) return piv;
	if(mici>k) return kthelem(st, mici-1);
	if(k>mari) return kthelem(mari+1, dr);
}