Cod sursa(job #1529568)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 21 noiembrie 2015 01:56:47
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
using namespace std;

void radixSort(int a[], int n) {
    int *b = new int [n];
    int *c = new int [n];

    for(int step = 0; step < 32; ++step) {
        int p = 0, q = 0;

        for(int i = 0; i < n; ++i) {
            if((a[i] & (1 << step)) == 0) {
                b[p++] = a[i];
            }
            else {
                c[q++] = a[i];
            }
        }
        int k = 0;
        for(int i = 0; i < p; ++i) {
            a[k++] = b[i];
        }
        for(int i = 0; i < q; ++i) {
            a[k++] = c[i];
        }
    }
}

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

    int n, a, b, c;
    f >> n >> a >> b >> c;

    int *v  = new int [n];
    v[0] = b;
    for(int i = 1; i < n; ++i) {
        v[i] = ((1LL * a * v[i - 1]) % c + b) % c;
    }

    radixSort(v, n);

    for(int i = 0; i < n; i += 10) {
        g << v[i] << " ";
    }
    g << "\n";

    f.close();
    g.close();

    return 0;
}