Cod sursa(job #375190)

Utilizator MciprianMMciprianM MciprianM Data 19 decembrie 2009 19:29:18
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
using namespace std;
#define MAXN 3000009
unsigned int a[MAXN], b[MAXN];
unsigned int *p1, *p2,*aux;
void rsort(unsigned int byte, unsigned int n){
	unsigned int frecv[256], i;
	memset(frecv, 0, sizeof(frecv));
	const unsigned int msk=255, rsh=byte*8;
	for(i=0;i<n;i++)
		frecv[((p1[i]>>rsh)&msk)]++;
	for(i=1;i<256;i++)
		frecv[i] += frecv[i-1];
	for(i=0;i<n;i++)
		p2[--frecv[((a[n-i-1]>>rsh)&msk)]]=p1[n-i-1];
	aux=p1;p1=p2;p2=aux;
}
int main(){
	unsigned int n, k, i;
	ifstream f("sdo.in");
	f>>n>>k;
	for(i=0;i<n;i++)
		f>>a[i];
	f.close();
	p1=a;p2=b;
	for(i=0;i<4;i++){
		rsort(i, n);
	}
	ofstream g("sdo.out");
	g<<a[--k]<<'\n';
	g.close();
	return 0;
}