Cod sursa(job #633353)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 13 noiembrie 2011 17:24:37
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>

using namespace std;

ifstream in("sdo.in");
ofstream out("sdo.out");

const int N=3000010;

int n,k,v[N];

void citire(){
	int i;
	in>>n>>k;
	for(i=1;i<=n;i++){
		in>>v[i];
	}
}

void schimba(int x,int y){
	int aux;
	aux=v[x];
	v[x]=v[y];
	v[y]=aux;
}

void Partition(int st,int dr){
	int i=st-1,j=dr+1,m=(st+dr)/2,pivot=v[st];
	while(i<j){
		do{
			i++;
		}while(v[i]<pivot);
		do{
			j--;
		}while(v[j]>pivot);
		if(j>i)
			schimba(i,j);
		else
			break;
	}
//	schimba(i,st);
	if(j==k){
		out<<v[j];
		return;
	}
	if(k<j)
		Partition(st,j-1);
	else{
		Partition(j+1,dr);
	}
}

int main(){
	citire();
	Partition(1,n);
	return 0;
}