Cod sursa(job #2911509)

Utilizator maiaauUngureanu Maia maiaau Data 30 iunie 2022 11:15:33
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;

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

const int N = 1e7;

unsigned a, b, c, k, i, V[N + 1], W[N + 1], *v, *w;
int n, poz[256];

inline unsigned gensecv(unsigned& x){
    x = 1ll * x * a % c;
    x = (x + b) % c;
    return x;
}
inline unsigned rot(unsigned x){
    return (x >> 8) | ((x & 255) << 24);
}

int main()
{
    f >> n >> a >> b >> c;
    unsigned x = b;
    v = V, w = W;
    for (i = 1; i <= n; i++){
        v[++k] = x;
        x = gensecv(x);
    }
    
    for(k = 0; k < 4; k++){
        for (i = 1; i <= n; i++) 
            poz[v[i] & 255]++;
        
        for (i = 1; i < 256; i++)
            poz[i] += poz[i - 1];
        
        for (i = n; i; i--){
            int q = v[i] & 255;
            w[poz[q]] = rot(v[i]);
            poz[q]--;
        }
        swap(v, w);
        memset(poz, 0, 255);
    }

    for (i = 1; i <= n; i += 10) g << v[i] << ' ';
    
    return 0;
}