Cod sursa(job #1280922)

Utilizator gerd13David Gergely gerd13 Data 2 decembrie 2014 18:15:14
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <vector>
#include <set>
#include <deque>
#include <queue>
#include <algorithm>
#include <map>
#include <limits>
#include <cstdlib>
#include <sstream>

using namespace std ;

const int NMAX = 10000010 ;
const int INF = 0x3f3f3f3f ;
const int BYTE = 8 ;


ifstream cin("radixsort.in") ;
ofstream cout("radixsort.out") ;


int N ;
long long  V[NMAX] ;

inline void READ()
{
    unsigned int A, B, C;
    cin >> N >> A >> B >> C ;

    V[1] = B % C;
    for(int i = 2 ; i <= N ; ++ i)
        V[i] =(1LL * A * V[i - 1] + B *1LL) % C ;


}
long long GET_BYTE(long long  val, long long byte)
{
    return (val >> (byte * BYTE)) & ((1 << BYTE) - 1) ;

}


inline void COUNT_SORT(int c_byte)
{
    vector <long long> suma[1 << BYTE] ;

    for(int i = 0 ; i < 1 << BYTE ; ++ i)
        suma[i].clear() ;

    for(int i = 1 ; i <= N ; ++ i)
        suma[GET_BYTE(V[i], c_byte)].push_back(V[i]) ;

    for(int i = 0, k = 0; i < 1<<BYTE ; ++ i)
        for(vector <long long> :: iterator it = suma[i].begin() ; it != suma[i].end() ; ++ it)
            V[++ k] = *it ;

}

inline void RADIX_SORT()
{

    for(int i = 0 ; i <= 3 ; ++ i)
        COUNT_SORT(i) ;
}

inline void OUT()
{
    for(int i = 1 ; i <= N ; i = i + 10)
        cout << V[i] << ' ' ;
    cout << '\n' ;

     /*for(int i = 1 ; i <= N ; i = i + 1)
        cout << V[i] << ' ' ;
    cout << '\n' ;
    */
}

int main()
{

    READ() ;
    RADIX_SORT() ;
    OUT() ;
    cin.close() ;
    cout.close() ;
    return  0 ;
}