Cod sursa(job #2445937)

Utilizator danielsociuSociu Daniel danielsociu Data 6 august 2019 11:38:23
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;
//#define st first
#define nd second
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORS(i,a,b) for(int i=(a);i<(b);++i)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<PII>
#define all(x) x.begin(),b.end()
#define SZ(x) ((int)(x).size())
#define ll long long
#define MOD 10000000 //998244353
const int inf=0x3f3f3f3f;
#define maxn 10000005

///buckets of bytes
#define maxb 8
#define bucket 0xFF //255,a byte aka bits 0-7(8 bits)
#define total_bytes (sizeof(vec[1]))
#define get_byte(x) ((x>>(byte*8))&bucket)

int n,a,b,c;

int* read(){
	cin>>n>>a>>b>>c;
	int *v=new int[n];
	v[0]=b;
	for(int i=1;i<n;++i)
		v[i]=(1LL*a*v[i-1]+b)%c;
	return v;
}

//int* countSort(int byte,int *vec){
void countSort(int byte,int *vec){
	int count[1<<maxb];
	int index[1<<maxb];
	int aux[n+5];
	//int *aux=new int[n];
	index[0]=0;
	memset(count,0,sizeof(count));

	FORS(i,0,n)
		count[get_byte(vec[i])]++;
	FORS(i,1,(1<<maxb))
		index[i]=index[i-1]+count[i-1];
	FORS(i,0,n)
		aux[index[get_byte(vec[i])]++]=vec[i];
	FORS(i,0,n)
		vec[i]=aux[i];
	//return aux;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("radixsort.in","r",stdin);
	freopen("radixsort.out","w",stdout);
	int *vec=read();
	for(int bit=0;bit<total_bytes;++bit)
		countSort(bit,vec);
		//vec=countSort(bit,vec);
	for(int i=0;i<n;i+=10)
		cout<<vec[i]<<' ';
}