Cod sursa(job #1937233)

Utilizator AhileGigel Frone Ahile Data 23 martie 2017 20:18:58
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<bits/stdc++.h>
using namespace std;
#define in f
#define out g

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

int const MAXSIZE = 10000010;

int n, a, b, c, maxx;
queue<int> q[20];
int ant, k[20], h, x;
vector<int> ans;


int main() {
    in >> n >> a >> b >> c;
    for (int i = 1; i <= n; i++) {
        x = (a * ant + b) % c;
        ant = x;
        maxx = max(maxx, x);
        q[x % 10].push(x);
    }
    while (maxx > 0) {
        maxx /= 10;
        h++;
    }
    for (int l = 1; l <= h; l++) {
        int p = 1;
        for (int i = 1; i < l; i++)
            p *= 10;
        for (int i = 0; i < 10; i++) {
            k[i] = q[i].size();
        }
        for (int i = 0; i < 10; i++) {
            for (int j = 1; j <= k[i]; j++) {
                int x = q[i].front();
                q[i].pop();
                int y = (x / p);
                y = y % 10;
                if (x < p)
                    ans.push_back(x);
                else
                    q[y].push(x);
            }
        }
    }
    for (int i = 0; i < 10; i++) {
        while (!q[i].empty()) {
            ans.push_back(q[i].front());
            q[i].pop();
        }
    }
    for (int i = 0; i < ans.size(); i++) {
        if (i % 10 == 0)
            out << ans[i] << " ";
    }
}