Cod sursa(job #1463473)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 21 iulie 2015 00:18:49
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <algorithm>
#define NMAX 10000007
FILE *fin, *fout;
using namespace std;
int n, a, b, c, v[NMAX];
char ret;
bool bit(int a, int k)
{
    return (a&(1<<k));
}
void radix(int st, int dr, int lvl)
{
    if(lvl < 0) return ;
    int i = st, j = dr;
    while(i < j)
    {
        while(bit(v[i], lvl) == 0 && i< j) ++i;
        while(bit(v[j], lvl) == 1 && i< j) --j;
        if(i < j) swap(v[i], v[j]);
    }
    if(bit(v[dr], lvl) == 0 || bit(v[st], lvl) == 1)
    {
        radix(st, dr, lvl-1);
        return ;
    }
    radix(st, i-1, lvl-1);
    radix(i, dr, lvl-1);
}
int main()
{
    fin = freopen("radixsort.in", "r", stdin);
    fout = freopen("radixsort.out", "w", stdout);
    scanf("%d %d %d %d", &n, &a, &b, &c);
    v[1] = b;
    for(int i = 2; i<= n; ++i) v[i] = (1LL*a*v[i-1] + b)%c;
    radix(1, n, 31);
    for(int i = 1; i<= n; i+=10) printf("%d ", v[i]); printf("\n");
    fclose(fin);
    fclose(fout);
    return 0;
}