Cod sursa(job #2540585)

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

long long OctetulP (long long x) {
    long long nr=x;
    nr=(nr>>(p*8));
    return (nr&255);
}

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

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

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

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*a[k][i-1]+B)%C;
    }
 //   fout<<19514%256<<"\n";
 //   fout<<19514/256;
    k=0;
    for (p=0;p<4;p++) {
        sortare(a[k],a[1-k]);
        stergere();
        k=1-k;
    }
    for(i=1;i<=n;i+=10) {
        fout<<a[1-k][i]<<" ";
    }
    return 0;
}