Cod sursa(job #1167520)

Utilizator andreiagAndrei Galusca andreiag Data 5 aprilie 2014 13:10:25
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <queue>
#include <bitset>

using namespace std;
const int Nmax = 100000005;
const int SZE = 256;

int d[4];
int s[4];
queue<int> b[2][SZE];

int main()
{
    ifstream f ("radixsort.in");
    ofstream g ("radixsort.out");

    d[0] = 0x000000ff;
    s[0] = 0;
    for (int i = 1; i < 4; i++)
    {
        d[i] = d[i-1] << 8;
        s[i] = s[i-1] + 8;
    }

    int N, B, C;
    long long A;
    f >> N >> A >> B >> C;
    // generarea numerelor
    int x = B;
    for(int i = 0; i < N; i++)
    {
        b[0][x & 0x000000ff].push(x);
        x = (A * x + B) % C;
    }

    int current = 0, next = 1;

    for (int k = 1; k < 4; k++)
    {
        for (int i = 0; i < SZE; i++)
        {
            int mask = d[k], shift = s[k];
            while (!b[current][i].empty())
            {
                x = b[current][i].front();
                    b[current][i].pop();
                b[next][(x & mask) >> shift].push(x);
            }
        }
        current = next; next = !next;
    }
    int k = 0;
    for (int i = 0; i < SZE; i++)
    {
        while(!b[current][i].empty())
        {
            if (!(k++ % 10))
                g << b[current][i].front() << ' ';
            b[current][i].pop();
        }
    }
    g << '\n';
    return 0;
}