Cod sursa(job #1837920)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 30 decembrie 2016 16:50:42
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>
 
using namespace std;
 
const int NMAX = 10000000;
const int SQRT = 1 << 16;
const int BUFFSIZE = (1 << 12);
 
char buf[BUFFSIZE];
int ptr = 0;
 
inline void putChar(const char &ch) {
    buf[ptr++] = ch;
    if (ptr == BUFFSIZE) {
        fwrite(buf, 1, BUFFSIZE, stdout);
        ptr = 0;
    }
}
 
inline void writeInt(int x) {
    char digs[10];
    int n = 0, q;
    do {
        q = x / 10;
        digs[n++] = x - (q << 1) - (q << 3) + '0';
        x = q;
    } while (x);
    while (n--) {
        putChar(digs[n]);
    }
    putChar(' ');
}
 
int fi[2 * SQRT + 1];
int v[NMAX];
int nxt[NMAX];
 
void bucketSort() {
    memset(fi, -1, sizeof fi);
    int n, a, b, c; scanf("%d%d%d%d", &n, &a, &b, &c);
    v[1] = b;
    for (int i = 1; i <= n; i++) {
    	long long aux = (long long)v[i - 1] * a + b;
    	v[i] = aux - aux / c * c;
        int j = v[i] & (SQRT - 1);
        nxt[i] = fi[j];
        fi[j] = i;
    }
    for (int i = SQRT - 1; i >= 0; i--) {
        int j = fi[i];
        while (j != -1) {
            int _nxt = nxt[j];
            int k = (v[j] >> 16) + SQRT;
            nxt[j] = fi[k];
            fi[k] = j;
            j = _nxt;
        }
    }
    int counter = 9;
    for (int i = SQRT; i <= 2 * SQRT; i++) {
        for (int j = fi[i]; j != -1; j = nxt[j]) {
        	if (++counter == 10) {
            	writeInt(v[j]);
            	counter = 0;
        	}
        }
    }
    fwrite(buf, 1, ptr, stdout);
}
 
int main() {
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    bucketSort();
    return 0;
}