Cod sursa(job #2654693)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 1 octombrie 2020 22:08:33
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
using namespace std;
ifstream  fin("radixsort.in");
ofstream fout("radixsort.out");
int N,A,B,C,*v;
void rs(int *v, long long r, int p, int q){
    if(r==0 || p>q)return;
    int i,j;
    i=p;j=q;
    while(i<=j && v[i]/r%2==0)i++;
    while(j>=i && v[j]/r%2==1)j--;
    while(i<j){
        int aux=v[i]; v[i]=v[j]; v[j]=aux;
        while(i<=j && v[i]/r%2==0)i++;
        while(j>=i && v[j]/r%2==1)j--;
    }
    rs(v,r/2,p,j);
    rs(v,r/2,j+1,q);
}
int main(){
    fin>>N>>A>>B>>C;
    v=new int[N+1];
    v[1]=B;
    for(int i=2;i<=N;i++){
        v[i] = ((long long)A * v[i-1] + B) % C;
    }

    rs(v,(long long)1<<31,1,N);

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

    fout.close();
    fin.close();
    return 0;
}