Cod sursa(job #2911525)

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

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

const int N = 1e7;

int a, b, c, n, i, k, x;
int v[N + 1], w[N + 1], cnt[256];

inline int gensir(int x){
    return ((1ll * x * a % c) + b) % c;
}
void radixsort(){
    for (int i = 0; i < 4; i++){
        for (int j = 1; j <= n; j++) 
            cnt[(v[j] >> (i * 8)) & 255]++;
        for (int j = 1; j < 256; j++)
            cnt[j] += cnt[j - 1];
        
        for (int j = n; j; j--){
            w[cnt[(v[j] >> (i * 8)) & 255]] = v[j];
            cnt[(v[j] >> (i * 8)) & 255]--;
        }
        swap(v, w);
        
        for (int j = 0; j < 256; j++) cnt[j] = 0;
    }
}

int main()
{
    f >> n >> a >> b >> c;
    x = b;
    for (int i = 1; i <= n; i++){
        v[++k] = x;
        x = gensir(x);
    }
    
    radixsort();
    
    for (int i = 1; i <= n; i += 10) g << v[i] << ' ';
    
    return 0;
}