Cod sursa(job #1168342)

Utilizator MKLOLDragos Ristache MKLOL Data 8 aprilie 2014 03:03:03
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<algorithm>
#include<vector>
#include<stdio.h>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define Nmax 10101010


using namespace std;
int v[Nmax];
int A,B,C,N;
void rsort(int st,int dr,int k){
    //printf("%d %d %d\n",st,dr,k);
    if(st <= 0 || dr > N)
        return;
    if(st >= dr)
        return;
    if(k<0)
        return;
    if(st==dr-1){
        if(v[st] > v[dr]){
            swap(v[st],v[dr]);
        }
        return;
    }
    int stx=st,drx=dr;
    while(stx<drx){

        while(((v[stx] & (1<<k)) == 0) && stx <= dr){
            ++stx;
        }
        while(((v[drx] & (1<<k)) == (1<<k)) && drx >= st){
            --drx;
        }
        if(stx<=drx)
        {
            int aux = v[stx];
            v[stx]=v[drx];
            v[drx]=aux;
        }
    }
    if(k>0){
    rsort(st,drx,k-1);
    rsort(drx+1,dr,k-1);
    }
}
int main(){
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&N,&A,&B,&C);
    v[1]=B;
    for(int i=2;i<=N;++i){
            v[i] = (1LL*A*v[i-1] + B) % C;
    }
    rsort(1,N,31);
    //sort(v+1,v+N+1);
    //printf("!!!");
    for(int i=1;i<=N;i+=10)
    {
        printf("%d ",v[i]);
    }
    return 0;
}