Cod sursa(job #1195564)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 7 iunie 2014 22:09:04
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <algorithm>
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<j and v[i]<=piv){
			if(v[i]<piv) v[mici++]=v[i];
			i++;
		}
		while(i<j 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--;
		}
	}
	if(i==j){
		if(v[i]<piv) v[mici++] = v[i];
		if(v[i]>piv) v[mari--] = v[i];
	}
	/*
	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");
	*/
	//printf("%d\n%d %d!!%d %d\n", piv, st, mici-1, mari+1, dr);
	if(mici<=k and k<=mari) return piv;
	if(mici>k) return kthelem(st, mici-1);
	if(k>mari) return kthelem(mari+1, dr);
}