Cod sursa(job #1393912)

Utilizator danalex97Dan H Alexandru danalex97 Data 19 martie 2015 20:51:51
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

ifstream F("radixsort.in");
ofstream G("radixsort.out");

const unsigned N = 10000010;
const unsigned sz = 12;
const unsigned M = 1<<sz;

unsigned n,x,y,z,a[N],b[N];
unsigned ct[M],mask=M-1;

void phase1()
{
    for (unsigned i=1;i<=n;++i) ct[a[i]&mask]++;
    for (unsigned i=1;i<M;++i) ct[i] += ct[i-1];
    for (unsigned i=M-1;i>0;--i) ct[i] = ct[i-1]+1; ct[0] = 1;
    for (unsigned i=1;i<=n;++i) b[ct[a[i]&mask]++] = a[i];
}

void phase2()
{
    for (unsigned i=0;i<M;++i) ct[i] = 0;
    for (unsigned i=1;i<=n;++i) ct[(b[i]&(mask<<sz))>>sz]++;
    for (unsigned i=1;i<M;++i) ct[i] += ct[i-1];
    for (unsigned i=M-1;i>0;--i) ct[i] = ct[i-1]+1; ct[0] = 1;
    for (unsigned i=1;i<=n;++i) a[ct[(b[i]&(mask<<sz))>>sz]++] = b[i];
}

void mysort()
{
    phase1();
    //for (unsigned i=1;i<=n;i+=10) cerr<<b[i]<<' ';
    phase2();
}

int main()
{
    F>>n>>x>>y>>z;
    a[1] = y;
    for (unsigned i=2;i<=n;++i)
        a[i] = (a[i-1] * x + y) % z;
    mysort();
    for (unsigned i=1;i<=n;i+=10)
        G<<a[i]<<' ';
    G<<'\n';
}