Cod sursa(job #373335)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 13 decembrie 2009 16:11:23
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fi("sdo.in");
ofstream fo("sdo.out");
int N,A[3000010],K;

int poz(int* A,int p,int u){
	int pivot=A[p+(rand()%(u-p+1))];
	int start=p,end=u;
	for (;1;){
		while (A[start]<pivot) ++start;
		while (A[end]>pivot) --end;
		if (start<end){ int aux=A[start];A[start]=A[end];A[end]=aux; }
		else return start;
	}
}

int kth_elem(int *A,int p,int u,int k){
	int m=poz(A,p,u);
	int x=m-p+1;
	if (x>k) return kth_elem(A,p,m-1,k); else 
		if (x<k)
		return kth_elem(A,m+1,u,k-x); else return A[m];
}

int main(){
	srand(time(NULL));
	fi>>N>>K;
	for (int i=1;i<=N;++i) fi>>A[i];
	fo<<kth_elem(A,1,N,K);
	fi.close();fo.close();
	return 0;
}