Cod sursa(job #2608744)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 1 mai 2020 18:24:44
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.74 kb
//
//  main.cpp
//  radixsort
//
//  Created by Eusebiu Rares on 01/05/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//
 
#include <iostream>
#include "fstream"

#pragma GCC optimize "O3"
 
class writer{
    public:
        writer() {};
        writer(const char *file_name){
            output_file.open(file_name,std::ios::out | std::ios::binary);
            output_file.sync_with_stdio(false);
            index=0;}
        inline writer &operator <<(int target){
            aux=0;
            n=target;
            if (!n)
                nr[aux++]='0';
            for (;n;n/=10)
                nr[aux++]=n%10+'0';
            for(;aux;inc())
                buffer[index]=nr[--aux];
            return *this;}
        inline writer &operator <<(const char *target){
            aux=0;
            while (target[aux])
                buffer[index]=target[aux++],inc();
            return *this;}
        ~writer(){
            output_file.write(buffer,index);output_file.close();}
    private:
        std::fstream output_file;
        static const int SIZE=0x200000;
        int index=0,aux,n;
        char buffer[SIZE],nr[24];
        inline void inc(){
            if(++index==SIZE)
                index=0,output_file.write(buffer,SIZE);}
};

std::fstream in ("radixsort.in", std::ios::in) ;
writer out ("radixsort.out") ;
 
inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
    unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
#ifdef __GNUC__
    asm(
        "divl %4; \n\t"
        : "=a" (d), "=d" (m)
        : "d" (xh), "a" (xl), "r" (y)
    );
#else
    __asm {
        mov edx, dword ptr[xh];
        mov eax, dword ptr[xl];
        div dword ptr[y];
        mov dword ptr[d], eax;
        mov dword ptr[m], edx;
    };
#endif
    out_d = d; out_m = m;
}

const int MV = 1e7 ;
 
int v[MV + 1] ;

typedef long long i64;
 
namespace raddix {

const int BITS = 12 ;
const int BASE = 1 << BITS ;
const int BASE_IND = BASE - 1 ;
 
void sort(int vec[], int size, int shift) {
	int i ;
	int nr[BASE + 1], aux[MV + 1], poz[BASE + 1] = {} ;
	for (shift ; shift < 32 ; shift += BITS) {
	
		std::fill(nr, nr + BASE, 0) ;
	
		for (i = 0 ; i < size ; ++ i) {
			nr[(vec[i] >> shift) & BASE_IND] ++ ;
		}
		poz[0] = 0 ;
		for (i = 1 ; i < BASE ; ++ i) { poz[i] = poz[i - 1] + nr[i - 1] ; }
		for (i = 0 ; i < size ; ++ i) {
			aux[poz[(vec[i] >> shift) & BASE_IND] ++] = vec[i] ;
		}
		for (i = 0 ; i < size ; ++ i) {
			vec[i] = aux[i] ;
		}
	}
}
}
 
int main(int argc, const char * argv[]) {
	int n, A, B, C ; in >> n >> A >> B >> C ;
	v[0] = B ;
	for (int i = 1 ; i < n ; ++ i) {
		v[i] = fasterLLMod(1ULL * v[i - 1] * A + B, C);
	}
	raddix::sort(v, n, 0) ;
	for (int i = 0 ; i < n ; i = i + 10) {
		out << v[i] << " " ;
	}
}