Cod sursa(job #2330855)

Utilizator DavidLDavid Lauran DavidL Data 28 ianuarie 2019 21:16:51
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fi("radixsort.in");
ofstream fo("radixsort.out");

const ll BASE = 1e5;

int n, a, b, c;
int v[10000005];
int v2[10000005];
int cnt[100005];

void radixSort()
{
    ll p = 1;
    for (int rep = 1; rep <= 2; rep++)
    {
        memset(cnt, 0LL, sizeof(cnt));

        p *= BASE;
        for (int i = 1; i <= n; i++)
            cnt[(v[i] / (p / BASE)) % BASE + 1]++;

        for (int i = 1; i <= BASE; i++)
            cnt[i] += cnt[i - 1];

        memset(v2, 0LL, sizeof(v2));
        for (int i = 1; i <= n; i++)
        {
            int poz = cnt[(v[i] / (p / BASE)) % BASE] + 1;
            v2[poz] = v[i];
            cnt[(v[i] / (p / BASE)) % BASE]++;
        }
        for (int i = 1; i <= n; i++)
            v[i] = v2[i];
    }
}

int main()
{
    fi >> n >> a >> b >> c;
    v[1] = b;
    for (int i = 2; i <= n; i++)
        v[i] = (ll)(1LL * a * v[i - 1] + b) % c;
    /*fi >> n;
    for (int i = 1; i <= n; i++)
        fi >> v[i];*/

    radixSort();

    for (int i = 1; i <= n; i += 10)
        fo << v[i] << " ";

    return 0;
}