Cod sursa(job #1424836)

Utilizator UAIC_HreapcaVlasNegrusUAIC Hreapca Vlas Negrus UAIC_HreapcaVlasNegrus Data 25 aprilie 2015 15:59:55
Problema Radix Sort Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <deque>
#include <vector>
#include <cstring>
#include <bitset>
#include <algorithm>
#define INF 1000010
#define uint unsigned int
#define ll long long
#define step(x) (x&(-x))
using namespace std;

uint N, A, B, C, i, cnt, mask[4], j;
vector<uint> v;

void radixsort(vector<uint> &V, uint step)
{
    if(step == 4)
    {
        int offset = 1 - cnt % 10;
        if(offset <= 0)
            offset = offset + 10;
        for(offset = offset - 1; offset < V.size(); offset += 10)
            printf("%d ", V[offset]);
        cnt = cnt + V.size();
        return;
    }
    vector<uint> chunk[257];
    for(int i = 0; i < V.size(); i++)
    {
        uint x = V[i];
        uint nr = (mask[step] & x) >> ((3-step)*8);
        chunk[nr].push_back(x);
    }
    for(uint i = 0; i < 256; i++)
    {
        if(chunk[i].size() > 1)
        {
            radixsort(chunk[i], step + 1);
            chunk[i].clear();
        }
        if(chunk[i].size() == 1)
        {
            cnt = cnt + 1;
            if(cnt % 10 == 1)
                printf("%d ",chunk[i][0]);
        }
    }
}


int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    mask[3] = (1<<8) - 1;
    mask[2] = mask[3] << 8;
    mask[1] = mask[2] << 8;
    mask[0] = mask[1] << 8;
    scanf("%d%d%d%d", &N, &A, &B, &C);
    v.push_back(B);
    for(i = 1; i < N; i++)
    {
        v.push_back((1LL * A * v[i-1] + B) % C);
    }
    radixsort(v, 0);
    return 0;
}