Cod sursa(job #2354192)

Utilizator shantih1Alex S Hill shantih1 Data 24 februarie 2019 23:29:48
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

#define nmx 10000005
#define rad_sz 256
#define sec(x) (x>>(8*byte))&255

using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

int n,i,j,nr,A,B,C;
int numb[nmx],loc[nmx],ind[rad_sz],cate[rad_sz];

void radix_sort(int A[],int B[],int byte)
{	
	memset(cate, 0, sizeof(cate));
	int i;
	for(i=1;i<=n;i++)
		++cate[sec(A[i])];
	
	ind[0]=1;
	for(i=1;i<=rad_sz;i++)
		ind[i]=ind[i-1]+cate[i-1];

	for(i=1;i<=n;i++)
		B[ind[sec(A[i])]++]=A[i];
}

int main() {
	
	fin>>n>>A>>B>>C;
	for(i=1;i<=n;i++)
	{
		if(i==1)	nr=B;
		else	nr=(1LL*nr*A+B)%C;
		numb[i]=nr;
	}
	
	for(i=0;i<4;i++)
	{
		if(!(i&1))	radix_sort(numb, loc, i);
		else	radix_sort(loc, numb, i);
	}
	
	for(j=11,i=1;i<=n;i++,j++)
	{
		if(j==11)
			fout<<numb[i]<<" ",	j=1;
	}
	/*
	 A fost odată ca-n povești,
	 A fost ca niciodată,
	 Din rude mari împărătești,
	 O prea frumoasă fată.
	 
	 Și era una la părinți
	 Și mândră-n toate cele,
	 Cum e Fecioara între sfinți
	 Și luna între stele.*/
}