Cod sursa(job #2814705)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 8 decembrie 2021 14:09:39
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream fi("radixsort.in");
ofstream fo("radixsort.out");
 
const int MAX_N = 10000007;

deque <unsigned int> bucket[2][256];
unsigned int i,n,a,b,c;
unsigned int v[MAX_N];
 
void radix_sort(unsigned int v[MAX_N], const unsigned int &n){
     unsigned int i;
      
     for(i=1;i<=n;i++)
       bucket[0][v[i]&((1<<8)-1)].push_back(v[i]);
        
     for(i=0;i<256;i++)
       while(!bucket[0][i].empty())
       {
        unsigned int &ref=bucket[0][i].front();
        bucket[1][(ref&((1<<16)-1))>>8].push_back(ref);
        bucket[0][i].pop_front();
       }
        
     for(i=0;i<256;i++)
       while(!bucket[1][i].empty())
       {
        unsigned int &ref=bucket[1][i].front();
        bucket[0][(ref&((1<<24)-1))>>16].push_back(ref);
        bucket[1][i].pop_front();
       }  
        
     for(i=0;i<256;i++)
       while(!bucket[0][i].empty())
       {
        unsigned int &ref=bucket[0][i].front();
        bucket[1][(ref&((1LL<<32)-1))>>24].push_back(ref);
        bucket[0][i].pop_front();
       } 
         
     unsigned int nr=0;
     for(i=0;i<256;i++)
       while(!bucket[1][i].empty())
       { 
        v[++nr]=bucket[1][i].front();
        bucket[1][i].pop_front(); 
       }
}
 
int main(){ 
    fi>>n>>a>>b>>c;
     
    v[1]=b;
    for(i=2;i<=n;i++)
      v[i]=(1LL*a*v[i-1]+1LL*b)%c;
     
    radix_sort(v,n);
     
    for(i=1;i<=n;i+=10)
      fo<<v[i]<<' ';
 
    fi.close();
    fo.close();
    return 0;
}