Cod sursa(job #2620330)

Utilizator ioanapintilie07Pintilie Ioana ioanapintilie07 Data 28 mai 2020 18:35:36
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>

using namespace std;

int buck[256][1000001];

void radixSort(int v[], int n) {
    int k, x, i, j, index;
    for (i = 0; i < 256; ++i)
        buck[i][0] = 0;
    for (k = 0; k < 32; k += 8) {
        for (i = 1; i <= n; ++i) {
            x = v[i] >> k & 255;
            buck[x][++buck[x][0]] = v[i];
        }
        index = 0;
        for (i = 0; i < 256; ++i) {
            for (j = 1; j <= buck[i][0]; ++j)
                v[++index] = buck[i][j];
            buck[i][0] = 0;
        }
    }
}

//v[i] = B, pentru i = 1
//v[i] = (A * v[i-1] + B) % C, pentru 2 ≤ i ≤ N

int v[1000001];

int main() {
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");
    int n, a, b, c, i;
    fin >> n >> a >> b >> c;
    v[1] = b;
    for (i = 2; i <= n; ++i)
        v[i] = (a * v[i-1] + b) % c;
    radixSort(v, n);
    for(i = 1; i <= n; i += 10)
        fout << v[i] << " ";
    fin.close();
    fout.close();
    return 0;
}