Cod sursa(job #1937034)

Utilizator AhileGigel Frone Ahile Data 23 martie 2017 17:03:55
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 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[10];
int v[MAXSIZE], k[10], h;
vector<int> ans;


int main() {
    in >> n >> a >> b >> c;
    for (int i = 1; i <= n; i++) {
        v[i] = (a * v[i - 1] + b) % c;
        maxx = max(maxx, v[i]);
      //  out << v[i] << " ";
        q[v[i] % 10].push(v[i]);
    }
    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();
            //out << k[i] << " ";
        }
        //out << p << endl;
        for (int i = 0; i < 10; i++) {
            for (int j = 1; j <= k[i]; j++) {
                int x = q[i].front();
               // out << x << "->" << x % p << " ";
                q[i].pop();
                int y = (x / p);
                y = y % 10;
                if (x < p)
                    ans.push_back(x);
                else
                    q[y].push(x);
            }
            //out << endl;
        }
    }
    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] << " ";
    }
}