Cod sursa(job #2676707)

Utilizator davidcotigacotiga david davidcotiga Data 24 noiembrie 2020 20:00:48
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stdio.h>
#include <string.h>

using namespace std;

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

#define MAX 10000000
#define MAXBITS 32
#define BITSPERSTEP 8

#define BASE (1 << BITSPERSTEP)      // 256
#define MASK (BASE - 1)              // 255

int v1[MAX], v2[MAX];
int freq[BASE], ind[BASE];

void sort(int* v, int* aux, int n, int bits) {
	if (bits == MAXBITS)
		return;

	memset(freq, 0, sizeof(freq));

	for (int i = 0; i < n; ++i)
		freq[v[i] >> bits & MASK]++;

	ind[0] = 0;
	for (int i = 1; i < BASE; ++i)
		ind[i] = ind[i - 1] + freq[i - 1];


	for (int i = 0; i < n; ++i)
		aux[ind[v[i] >> bits & MASK]++] = v[i];

	sort(aux, v, n, bits + BITSPERSTEP);
}

int main() {
	int n, a, b, c;

	fin >> n >> a >> b >> c;

	v1[0] = b;

	for (int i = 1; i < n; ++i)
		v1[i] = (1LL * a * v1[i - 1] + b) % c;

	sort(v1, v2, n, 0);

	for (int i = 0; i < n; i += 10)
		fout << v1[i] << " ";


	return 0;
}