Cod sursa(job #1774257)

Utilizator danielNiculaeDaniel Niculae danielNiculae Data 8 octombrie 2016 18:54:28
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include "fstream"

//using namespace std;

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

const int NMAX = 10000015;
const int DIGITS = 12;

unsigned int a[NMAX];
unsigned int ordered[NMAX];
int cnt[DIGITS + 5];


void radix(long long pow, int N) {

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

    for(int i = 1 ; i <= N ; i++) {
        cnt[(a[i]%pow)/(pow/10)]++;
    }

    for(int i = 1 ; i < DIGITS; i++) {
        cnt[i] += cnt[i - 1];
    }


    for(int i = N ; i ; i--) {
        if(cnt[(a[i]%pow)/(pow/10)] < 0) {
            break;
        }
        ordered[cnt[(a[i]%pow)/(pow/10)]--] = a[i];
    }

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

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

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


    for(long long pow = 10 ; pow <= 10000000000 ; 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";

    return 0;
}