Cod sursa(job #2697370)

Utilizator OctavianVasileVasileOctavian OctavianVasile Data 18 ianuarie 2021 13:24:27
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
#define NMAX 10000003
int n, m, a, b, c;
long long k;
int v [NMAX], t [NMAX];
int u [256];
void radix_sort (int n, int v [], int t [], int x){
    memset (u, 0, sizeof (u));
    for (int i = 1; i <= n; i ++)
        u [v [i] >> x & 255] ++;
    for (int i = 255; i > 0; i --)
        u [i] = u [i - 1];
    u [0] = 0;
    for (int i = 1; i <= 255; i ++)
        u [i] += u [i - 1];
    for (int i = 1; i <= n; i ++)
        t [++ u [v [i] >> x & 255]] = v [i];
}
int main (){
    fin >> n >> a >> b >> c;
    for (int i = 1; i <= n; i ++)
        v [i] = (1LL * a * v [i - 1] + b) % c;
    radix_sort (n, v, t, 0);
    radix_sort (n, t, v, 8);
    radix_sort (n, v, t, 16);
    radix_sort (n, t, v, 24);
    for (int i = 1; i <= n; i += 10)
        fout << v [i] << " ";
    return 0;
}