Cod sursa(job #1773414)

Utilizator danielNiculaeDaniel Niculae danielNiculae Data 7 octombrie 2016 20:23:03
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include "fstream"

using namespace std;

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

const int NMAX = 10000005;
const int DIGITS = 12;

int a[NMAX];
int ordered[NMAX];


void radix(int pow, int N) {
    int count[DIGITS];

    for(int i = 0 ; i <= DIGITS ; i++) {
        count[i] = 0;
    }

    for(int i = 1 ; i <= N ; i++) {
        count[(a[i]%pow)/(pow/10)]++;
    }
    for(int i = 1 ; i < DIGITS; i++) {
        count[i] += count[i - 1];
//        fout << count[i] << " ";

    }
//    fout << "\n";
//    fout.flush();

    for(int i = N ; i ; i--) {
//        fout << (a[i]%pow)/(pow/10) << "\n";
//        fout.flush();
        ordered[count[(a[i]%pow)/(pow/10)]--] = a[i];
    }

//    for(int i = 1 ; i <= N; i++) {
//        fout << ordered[i] << " ";
//    }
//    fout << "\n";
//    fout.flush();


    for(int i = 1 ; i <= N ; i++) {
        a[i] = ordered[i];
    }
}

int main() {
    int N, A, B, C;

    fin >> N >> A >> B >> C;
    a[1] = B;
    for(int i = 2 ; i <= N ; i++) {
        a[i] = (A * a[i - 1] + B) % C;
    }


    for(int pow = 10 ; pow <= N*10 ; pow *= 10) {
//        for(int i = 1 ; i <= N ; i++) {
//            fout << a[i] << " ";
//        }
//        fout << "\n";

        radix(pow, N);
    }

    for(int i = 1 ; i <= N ; i += 10) {
        fout << a[i] << " ";
    }
    fout << "\n";
}