Cod sursa(job #1997087)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 3 iulie 2017 12:45:30
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int sz = 10000001;
const int base = 0x100;
const int byte = 0xFF;

int getDigits(int num);

int _values[sz], _tempValues[sz];
int *values=_values, *tempValues=_tempValues;
int counter[base];
int pos[base];

int main() {
    int num, a, b, c, i, power;
    in >> num >> a >> b >> c;
    values[1] = b % c;
    for( i = 2; i <= num; i++ ) {
        values[i] = (1LL * a * values[i-1] % c + b) % c;
    }
    for( power = 0; power != 32; power += 8 ) {
        memset(counter, 0, sizeof(counter));
        for( i = 1; i <= num; i++ ) {
            ++counter[(values[i]>>power)&byte];
        }
        pos[0] = 1;
        for( i = 1; i < base; i++ ) {
            pos[i] = pos[i-1] + counter[i-1];
        }
        for( i = 1; i <= num; i++ ) {
            tempValues[pos[(values[i]>>power)&byte]++] = values[i];
        }
        swap(values, tempValues);
    }
    for( i = 1; i <= num; i += 10 ) {
        out << values[i] << ' ';
    }
    out << '\n';
    in.close();
    out.close();
    return 0;
}