Cod sursa(job #1492209)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 27 septembrie 2015 12:50:34
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <queue>
#include <algorithm>

#define MaxN 10000005

using namespace std;

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

int N, A, B, C, v[MaxN];
queue<int> q[10];

int main() {
    fin >> N >> A >> B >> C;

    int largestNumber = B;
    v[1] = B;
    for (int i = 2; i <= N; ++i) {
        v[i] = (1LL * A * v[i - 1] + B) % C;
        largestNumber = max(largestNumber, v[i]);
    }

    int iterCount = 0;
    while (largestNumber > 0) {
        largestNumber /= 10;
        ++iterCount;
    }

    int d = 1;
    for (; iterCount > 0; --iterCount) {
        for (int i = 1; i <= N; ++i) {
            int divisor = v[i] / d;
            q[divisor % 10].push(v[i]);
        }

        int k = 0;
        for (int i = 0; i <= 9; ++i) {
            while (!q[i].empty()) {
                v[++k] = q[i].front();
                q[i].pop();
            }
        }
        d *= 10;
    }

    for (int i = 1; i <= N; i += 10) {
        fout << v[i] << ' ';
    }

    return 0;
}