Cod sursa(job #2687372)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 19 decembrie 2020 22:24:58
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("radixsort.in");
ofstream g("radixsort.out");

int v[10000005];
int aux[10000005];
long p10[12];
int n;
int digit[11];
int a,b,c;
int maxnr;
int aa;

void init_array() {
    for (int i=1;i<=n;i++) {
        v[i] = aux[i-1];
    }
    for (int i=0;i<=9;i++) {
        digit[i]=0;
    }
}

void init_p10() {
    p10[0]=1;
    for (int i=1;i<=11;i++) {
        p10[i] = p10[i-1]*10;
    }
}

int main()
{
    init_p10();
    f >> n >> a >> b >> c;
    v[1] = b;
    maxnr = b;
    for (int i=2;i<=n;i++) {
        v[i] = (a*v[i-1]+b)%c;
        maxnr = max(maxnr,v[i]);
    }
    while (maxnr/p10[aa]!=0) {
        for (int i=1;i<=n;i++) {
            digit[(v[i]/p10[aa])%10+1]++;
        }
        for (int i=1;i<=9;i++) {
            digit[i] += digit[i-1];
        }
        for (int i=1;i<=n;i++) {
            aux[digit[(v[i]/p10[aa])%10]] = v[i];
            digit[(v[i]/p10[aa])%10]++;
        }
        init_array();
        aa++;
    }
    for (int i=1;i<=n;i+=10) {
        g << v[i] << " ";
    }
    return 0;
}