Nu exista pagina, dar poti sa o creezi ...
Cod sursa(job #2955016)
Utilizator | Data | 15 decembrie 2022 22:19:40 | |
---|---|---|---|
Problema | Radix Sort | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.36 kb |
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 10000000;
const long long HASH = 128; ///Putem sorta dupa cifre si in alte baze. Aici folosim baza = HASH.
int n;
int v[1 + NMAX];
int aux[1 + NMAX];
int cifre[HASH];
void sortAux(long long putereHash)
{
for (int i = 0; i < HASH; i++)
cifre[i] = 0;
for (int i = 1; i <= n; i++)
cifre[v[i] / putereHash % HASH]++;
for (int i = 1; i < HASH; i++)
cifre[i] += cifre[i - 1];
for (int i = n; i >= 1; i--)
{
aux[cifre[(v[i] / putereHash) % HASH]] = v[i];
cifre[(v[i] / putereHash) % HASH]--;
}
for (int i = 1; i <= n; i++)
v[i] = aux[i];
}
void radixSort()
{
int maxim = -1;
for (int i = 1; i <= n; i++)
maxim = max(maxim, v[i]);
for (long long putereHash = 1; putereHash <= maxim; putereHash *= HASH)
sortAux(putereHash);
}
int main()
{
ios_base::sync_with_stdio(false);
ifstream in("radixsort.in");
ofstream out("radixsort.out");
long long a, b, c;
in >> n >> a >> b >> c;
v[1] = b;
for (int i = 2; i <= n; i++)
v[i] = (a * v[i - 1] + b) % c;
radixSort();
for (int i = 1; i <= n; i += 10)
out << v[i] << ' ';
out << '\n';
in.close();
out.close();
return 0;
}