Cod sursa(job #2596053)

Utilizator As932Stanciu Andreea As932 Data 9 aprilie 2020 10:31:08
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

void radixsort(vector <int>& v)
{
    vector <int> cnt(256);
    vector <int> out(v.size());

    for(int bit=0;bit<=31;bit+=8)
    {
        for(auto& x : v)
            cnt[(x>>bit) & 255]++;

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

        for(int i=v.size()-1;i>=0;i--)
            out[--cnt[(v[i]>>bit) & 255]]=v[i];

        v=out;

        fill(cnt.begin(),cnt.end(),0);
    }
}

void display(vector <int>& v)
{
    for(int i=0;i<v.size();i+=10)
        fout<<v[i]<<" ";
}

int main()
{
    int n,a,b,c;
    fin>>n>>a>>b>>c;

    vector <int> v(n);

    v[0]=b;
    for(int i=1;i<n;i++)
        v[i]=(1LL*a*v[i-1]+b)%c;

    radixsort(v);
    display(v);

    return 0;
}