Cod sursa(job #663287)

Utilizator i_am_testerCont Teste i_am_tester Data 18 ianuarie 2012 10:25:55
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int N=10000;

int v[3000001],frecv[N];

int maxim=0,minim=1000000001;

int n,I,k;

void solve(){
	int i;
	maxim=0;
	minim=1000000001;
	memset((void*)&frecv, 0, sizeof(int)*N);
	for(i=1;i<=n;i++){
		if(v[i]>maxim)
			maxim=v[i];
		if(v[i]<minim)
			minim=v[i];
	}
	I=(maxim-minim+1)/N+1;
	for(i=1;i<=n;i++){
		frecv[(v[i]-minim+1)/I]++;
	}
	int frecvtotal=0;
	int poz=0;
	for(i=0;i<=N;i++){
		frecvtotal+=frecv[i];
		if(frecvtotal>=k){
			poz=i;
			frecvtotal-=frecv[i];
			break;
		}
	}
	k-=frecvtotal;
	int aux=0;
	for(i=1;i<=n;i++){
		if((v[i]-minim+1)/I==poz){
			v[++aux]=v[i];
		}
	}
	n=aux;
	if(aux==1){
		out<<v[1];
		return;
	}
	solve();
}

int main(){
	int i;
	in>>n>>k;
	for(i=1;i<=n;i++){
		in>>v[i];
		if(v[i]>maxim)
			maxim=v[i];
		if(v[i]<minim)
			minim=v[i];
	}
	solve();
	return 0;
}