Cod sursa(job #2660981)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 20 octombrie 2020 23:33:32
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <type_traits>
#include <random>
#include <cstring>
#include <stack>
#include <stdlib.h>
#include <map>
#include <set>
using namespace std;
#define SERVER 0
const string nameFile="radixsort";
ifstream in (nameFile+".in");
ofstream out(nameFile+".out");
typedef long long ll;
#if (SERVER)
    #define in cin
    #define out cout
#endif
namespace sortingUtils{
    template<typename T, class RandomIt>
    void radixSort(RandomIt p1, RandomIt p2){
        const int sz=(is_same<T, long long int>::value) ? 8 : 4;
        vector <T> sec(p2-p1+1);
        int nr[256];
        for(int cnt=0; cnt<sz; cnt++){
            memset(nr, 0, sizeof(int)*256);
            for(RandomIt ptr=p1; ptr!=p2; ptr++) nr[(*ptr)>>(8*cnt)&255]++;
            for(int i=255; i; i--) nr[i]=nr[i-1]; nr[0]=0;
            for(int i=1; i<256; i++) nr[i]+=nr[i-1];
            for(RandomIt ptr=p1; ptr!=p2; ptr++)
                sec[nr[(*ptr)>>(8*cnt)&255]++]=(*ptr);
            for(RandomIt ptr=p1; ptr!=p2; ptr++)
                (*ptr)=sec[ptr-p1];
        }
    }
}
const int nmax=1e7;
int v[nmax];
long long n, a, b, c;
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    in>>n>>a>>b>>c;
    v[0]=b;
    for(int i=1; i<n; i++){
        v[i]=(int)(a*v[i-1]+b)%c;
    }
    sortingUtils::radixSort<int>(v, v+n);
    for(int i=0; i<n; i+=10)
        out<<v[i]<<" ";
    return 0;
}