Cod sursa(job #2661000)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 21 octombrie 2020 00:32:26
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 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);

        int nr[256];
        for(int cnt=0; cnt<sz; cnt+=2){
            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);

            memset(nr, 0, sizeof(int)*256);
            for(int i=0; i<sec.size(); i++) nr[(sec[i]>>(8*cnt+8))&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(int i=0; i<sec.size(); i++)
                *(p1+nr[(sec[i]>>(8*cnt+8))&255]++)=sec[i];
        }
    }
}
const int nmax=10000000;
int v[nmax+1];
unsigned 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)((unsigned long long)v[i-1]*a+b)%c;
    }
    sortingUtils::radixSort<int>(v, v+n);
    for(int i=0; i<n; i+=10)
        out<<v[i]<<" ";
    return 0;
}