Cod sursa(job #651641)

Utilizator codrina_91Pintea codrina codrina_91 Data 20 decembrie 2011 23:34:33
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <iostream>
#include <cmath>

using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");

int v[3000000],n,k,i,leg[3000000];
int m,cap=0,maxi,a;

void radix_sort()
{
	int p[256],u[256]; 
	int i,j,k,l,d=256;
	//golim cozi
	for (i=0;i<n;i++)
		leg[i]=i+1;
	//facem de m ori distribuirea
	for (i=1;i<=4;i++)
	{
		for (j=0;j<256;j++)
		p[j]=u[j]=-1;
		l=cap;
		for (j=0;j<n;j++)
		{
			k=(v[l]>>(i*8-8))&(d-1);//sa incerc cu o var globala
			
			if (p[k]==-1) p[k]=u[k]=l;
			else 
			{
				leg[u[k]]=l;u[k]=l;//5 3 6 8 1 6 8 3 48 999
			}
			l=leg[l];
		}
		//leg cozi
		j=0;
		while (p[j]==-1) 
			j++;
		cap=p[j];
		while (j<256)
		{
			for (k=j+1;k<256;k++)
				if (p[k]!=-1)
				{//fac legatura
					leg[u[j]]=p[k];
					break;
				}
			j=k;
		}
		d=d*256;
	}
}

int main()
{
	f>>n;f>>k;
	for (i=0;i<n;i++)
		f>>v[i];
	
	radix_sort();
	a=cap;
	for (i=2;i<=k;i++)
		a=leg[a];
	g<<v[a];
	return 0;
}