Cod sursa(job #1905128)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 5 martie 2017 22:07:22
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <bits/stdc++.h>

using namespace std;

const int kBucket = 1 << 16, kMaxN = 10000000;

inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
    unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
#ifdef __GNUC__
    asm(
        "divl %4; \n\t"
        : "=a" (d), "=d" (m)
        : "d" (xh), "a" (xl), "r" (y)
    );
#else
    __asm {
        mov edx, dword ptr[xh];
        mov eax, dword ptr[xl];
        div dword ptr[y];
        mov dword ptr[d], eax;
        mov dword ptr[m], edx;
    };
#endif
    out_d = d; out_m = m;
}
 
//x / y < 2^32 !
inline unsigned fasterLLMod(unsigned long long x, unsigned y) {
    unsigned dummy, r;
    fasterLLDivMod(x, y, dummy, r);
    return r;
}


int head[2 * kBucket], 
    value[kMaxN], to[kMaxN];

char Buff[1 << 17];
int buffPos;

inline void PutChar(const char& ch) {
    Buff[buffPos++] = ch;
    
    if(buffPos == (1 << 17)) {
        fwrite(Buff, 1, 1 << 17, stdout);
        buffPos = 0;
    }
}

inline void WriteInteger(int x) {
    char digits[10];
    int n = 0, q;
    do {
        q = x / 10;
        digits[n++] = x - (q << 1) - (q << 3) + '0';
        x = q;
    } while (x);
    
    while(n--)
        PutChar(digits[n]);
        
    PutChar(' ');
}

int main() {
#ifdef INFOARENA
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
#endif

    int n, a, b, c;
    scanf("%d%d%d%d", &n, &a, &b, &c);
    b %= c;
    
    memset(head, -1, sizeof head);    
    
    int x = 0;
    for(int i = 0; i < n; ++i) {
        x = fasterLLMod(b + 1ULL * x * a, c);
        
        const int where = x & (kBucket - 1);
        value[i] = x;
        to[i] = head[where];
        head[where] = i;
    }
    
    for(int i = kBucket - 1; ~i; --i) {
        int j = head[i];    
        while(j != -1) {
            const int prev_to = to[j];
            const int where = kBucket + (x >> 16);
            
            to[j] = head[where];
            head[where] = j;
            j = prev_to;
        }
    }
    
    int counter = 9;
    for(int i = 0; i < kBucket; ++i)
        for(int x = head[kBucket + i]; x != -1; x = to[x])
            if(++counter == 10) {
                WriteInteger(value[x]);
                counter = 0;
            }
            
    fwrite(Buff, 1, buffPos, stdout);
            
}