Cod sursa(job #651661)

Utilizator codrina_91Pintea codrina codrina_91 Data 21 decembrie 2011 00:17:01
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 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);
			if (p[k]==-1) p[k]=u[k]=l;//255 256 255 256 65536 65535
			else 
			{
				leg[u[k]]=l;u[k]=l;
			}
			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;
		}
	}
}

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];
	/*f<<1000<<" ";
	f<<5<<" "<<endl;
	for (int i=1;i<=1000;i++)
		f<<2000-i<<" ";
		
	return 0;*/
}