Cod sursa(job #604125)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 20 iulie 2011 15:57:05
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <iostream>

using namespace std;

void radix_sort(int byte, int n ,unsigned long *src, unsigned long *dest)
{
	unsigned long count[256]={0};
	unsigned long index[256]={0};
	for(int i=0; i<n; ++i)
		count[(src[i]>>(byte<<3))&0xff]++;
	for(int i=1; i<256; ++i)
		index[i]=index[i-1]+count[i-1];
	for(int i=0; i<n; ++i)
		dest[index[(src[i]>>(byte<<3))&0xff]++]=src[i];
}

unsigned long count[(1<<16)+1];
unsigned long index[(1<<16)+1];

void radix_sort16(int byte, int n ,unsigned long *src, unsigned long *dest)
{
	for(int i=0; i<n; ++i)
		count[(src[i]>>(byte<<3))&0xffff]++;

	for(int i=1; i<(1<<16); ++i)
		index[i] = index[i-1]+count[i-1];

	for(int i=0; i<n; ++i)
		dest[index[(src[i]>>(byte<<3))&0xffff]++] = src[i];
}


int main()
{
	int n, k;
	unsigned long *a, *b;
	fstream fin("sdo.in", fstream::in);
	fstream fout("sdo.out", fstream::out);
	
	fin >> n >> k;
	a=new unsigned long[n];
	b=new unsigned long[n];
	
	for (int i=0; i<n; ++i)
	{
		fin >> a[i];
	}
	
	/*radix_sort(0,n,a,b);
	radix_sort(1,n,b,a);
	radix_sort(2,n,a,b);
	radix_sort(3,n,b,a);*/
	
	radix_sort16(0,n,a,b);
	radix_sort16(1,n,b,a);
	
	/*for (int i=0; i<n; ++i)
	{
		cout << b[i] << " ";
	}*/
	
	//cout << endl;
	
	fout << b[k-1] << "\n";
	
	fin.close();
	fout.close();
	return 0;
}