Cod sursa(job #2354155)

Utilizator shantih1Alex S Hill shantih1 Data 24 februarie 2019 22:23:32
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>

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

int n,i,j,nr,A,B,C;

struct radix
{	int c[4],k;	} x;
vector<radix> ad[300],v;

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;
		x.c[0]=x.c[1]=x.c[2]=x.c[3]=0;
		x.k=nr;
		
		for(j=0;j<8;j++)
			if((1<<j)&nr)	x.c[0]+=1<<j;
		for(j=8;j<16;j++)
			if((1<<j)&nr)	x.c[1]+=1<<(j-8);
		for(j=16;j<24;j++)
			if((1<<j)&nr)	x.c[2]+=1<<(j-16);
		for(j=24;j<32;j++)
			if((1<<j)&nr)	x.c[3]+=1<<(j-24);
				
		ad[x.c[0]].push_back(x);
	}
	for(i=1;i<4;i++)
	{
		for(j=256;j>=0;j--)
			while(!ad[j].empty())
			{
				v.push_back(ad[j].back());
				ad[j].pop_back();
			}
		while(!v.empty())
		{
			ad[v.back().c[i]].push_back(v.back());
			v.pop_back();
		}
	}
	nr=10;
	for(i=0;i<=256;i++)
		for(auto l:ad[i])
		{
			nr++;
			if(nr==11)
			{
				fout<<l.k<<" ";
				nr=1;
			}
		}
}