Cod sursa(job #2950679)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 4 decembrie 2022 14:31:50
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
const int nr = 8;
int v[10000000],n;
vector <int> f[nr];
//vector <int> f[nr];
void radixsort(int l,int r,int bit){
    if(l >= r)return;
    //for(int i = 0;i < nr;i++)f[i].clear();
    int s[nr];
    for(int i = 0;i < nr;i++){
        f[i].clear();
        s[i] = 0;
    }
    for(int i = l;i <= r;i++){
        f[(v[i]/bit)%nr].push_back(v[i]);
        s[(v[i]/bit)%nr]++;
        //cout<<(v[i]/bit)%nr<<' '<<v[i]<<' '<<bit<<'\n';
    }
    int cnt = 0;
    for(int i = 0;i < nr;i++){
        for(auto j:f[i]){
            v[l + cnt++] = j;
        }
    }
    if(bit != 1){
        int cur = 0;
        for(int i = 0;i < nr;i++){
            //cout<<"recursion:"<<cur<<' '<<cur + f[i].size() - 1<<'\n';
            radixsort(cur + l,l + cur + s[i] - 1,bit/nr);
            cur+=s[i];
        }
    }
}
int main(){
    int a,b,c,i;
    fin>>n>>a>>b>>c;
    v[0] = b;
    for(i = 1;i < n;i++){
        v[i] = (1ll*v[i - 1]*a + b)%c;
    }
    radixsort(0,n - 1,(1<<30));
    for(i = 0;i < n;i+=10)fout<<v[i]<<' ';
    return 0;
}