Cod sursa(job #2814704)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 8 decembrie 2021 14:07:56
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
using namespace std;

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(){
    ifstream cin("radixsort.in");
    ofstream cout("radixsort.out");

    cin >> n >> a >> b >> c;

    v[1] = b;
    for(unsigned int i = 2; i <= n; ++i){
        v[i] = (a * 1LL * v[i - 1] + b) % c;
    }

    radix_sort(v, n);

    for(int i = 1; i <= n; i += 10){
        cout << v[i] << " ";
    }

    cin.close();
    cout.close();
    return 0;
}