Pagini recente » Cod sursa (job #906354) | Cod sursa (job #1206213) | Cod sursa (job #351551) | Cod sursa (job #2731626) | Cod sursa (job #2608753)
//
// 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;
}
inline unsigned fasterLLMod(unsigned long long x, unsigned y) {
unsigned dummy, r;
fasterLLDivMod(x, y, dummy, r);
return r;
}
const int MV = 1e7 ;
int v[MV + 1] ;
typedef long long i64;
namespace raddix {
const int BITS = 8 ;
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] << " " ;
}
}