Cod sursa(job #1889322)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 22 februarie 2017 17:56:38
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;

#define DIG_SIZE 255

int N, A, B, C, X;
vector<int> v;
queue<int> b[DIG_SIZE];

void radix() {

    for (int i = 0; i < 32; i += 8) {
        for (int j = 0; j < N; ++j) {
            b[(v[j] >> i) & DIG_SIZE].push(v[j]);
        }
        int n = 0;
        for (int j = 0; j < DIG_SIZE; ++j) {
            while (!b[j].empty()) {
                v[n++] = b[j].front();
                b[j].pop();
            }
        }
    }
}

int main() {

freopen("radixsort.in","r",stdin);
freopen("radixsort.out","w",stdout);

    cin >> N >> A >> B >> C;
    //N = 100; A = 12; B = 38; C = 123;
    v.push_back(B);
    X = B;
    for (int i = 1; i < N; ++i) {
        X = ((long long)A * X + B) % C;
        v.push_back(X);
    }
    radix();
    for (int i = 0; i < v.size(); ++i) {
        if (i % 10 == 0) {
            printf("%d ", v[i]);
        }
    }

    return 0;
}