Cod sursa(job #2375045)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 7 martie 2019 22:00:37
Problema Radix Sort Scor 70
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 0.97 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int n, a, b, c;
int v[10000002], v2[10000002];
int sm[260];
int main()
{
    f >> n >> a >> b >> c;
    v[1] = b;
    for(int i = 2; i <= n; ++i)
    {
        long long z = (1LL * a * v[i-1] + b) % c;
        v[i] = z;
    }
    int nrb = (1<<8) - 1;
    for(int i = 0; i <= 3; ++i)
    {
        memset(sm, 0, sizeof(sm));
        for(int j = 1; j <= n; ++j)
        {
            int xx = (v[j] & nrb);
            xx >>= (8 * i);
            sm[xx + 1]++;
        }
        for(int j = 1; j <= 255; ++j)
            sm[j] += sm[j-1];
        int pz = 0;
        for(int j = 1; j <= n; ++j)
        {
            int xx = (v[j] & nrb);
            xx >>= (8 * i);
            v2[++sm[xx]] = v[j];
        }
        memcpy(v, v2, sizeof(v2));
        nrb <<= 8;
    }
    for(int j = 1; j <= n; j += 10)
        g << v[j] << " ";
    return 0;
}