Cod sursa(job #2947912)

Utilizator TheEpicWipedCreaVlad Chirita Alexandru TheEpicWipedCrea Data 26 noiembrie 2022 21:32:28
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in  ("radixsort.in");
ofstream out("radixsort.out");

#define MAX_N 10000000
#define SignificantBit 30

int v[MAX_N];

void rasort(int st,int dr,int BitNr){
    if(st>=dr || BitNr==-1){
        return;
    }

    int pos=st;
    for(int i=st;i<=dr;i++){
        if((v[i] & (1<<BitNr))==0) {
            int aux=v[i];
            v[i]=v[pos];
            v[pos]=aux;
            pos++;
        }
    }

    rasort(st,pos-1,BitNr-1);
    rasort(pos,dr,BitNr-1);
}

int main() {
    int n,a,b,c;
    in>>n>>a>>b>>c;

    long long last=0;
    for(int i=0;i<n;i++){
        long long now=(long long)(a*last+b)%c;
        last=now;
        v[i]=now;
    }

    rasort(0,n-1,SignificantBit);

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