Cod sursa(job #663254)

Utilizator i_am_testerCont Teste i_am_tester Data 18 ianuarie 2012 09:48:25
Problema Statistici de ordine Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N=3000001;

int v[N],frecv[N+100000];

int maxim=0,minim=1000000001;

int n,I,k;

void solve(){
	int i;
	maxim=0;
	minim=1000000001;
	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]/I]++;
	}
	int frecvtotal=0;
	int poz=0;
	for(i=1;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]/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;
}