Cod sursa(job #2540625)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 7 februarie 2020 13:06:13
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#define dim 10000010
using namespace std;
int a[2][dim];
int f[270];
int i,n,p,k,A,B,C,P;

inline int OctetulP (int x) {
    return ((x >> P)&255);
}

void stergere() {
    for (int i=0;i<=256;i++) {
        f[i]=0;
    }
}

void sumaPartiala() {
    for (int i=1;i<=255;i++) {
        f[i]+=f[i-1];
    }
}

void sortare (int a[],int b[]) {
    int x;
    for (int i=1;i<=n;i++) {
        f[OctetulP(a[i])]++;
    }
    sumaPartiala();
    for (int i=n;i>=1;i--) {
        b[f[x = OctetulP(a[i])]]=a[i];
        f[x]--;
    }
}

int main() {
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");
    fin>>n>>A>>B>>C; ///nr&255=valoarea reprezentata de ultimul octet al numarului
    a[k][1]=B;       ///nr>>p*8=numarul fara ultimul octet
    for (i=2;i<=n;i++) {
        ///a[k][i]=((1LL*(A%C)*1LL*(a[k][i-1])%C)%C+1LL*B)%C;
        a[k][i] = (A * 1LL * a[k][i-1] + B) % C;
    }
 //   fout<<19514%256<<"\n";
 //   fout<<19514/256;
    k=0;
    P = 0;
    for (p=0;p<4;p++) {
        sortare(a[k],a[1-k]);
        stergere();
        P += 8;
        k=1-k;
    }
    for(i=1;i<=n;i+=10) {
        fout<<a[k][i]<<" ";
    }
    return 0;
}