Cod sursa(job #2856870)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 24 februarie 2022 14:51:14
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;

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

int v[2][10000005];
int a,b,c,n;
int digit[257];
int maxx;
int pw=1;
int ops=1;

void solve() {
    f >> n >> a >> b >> c;
    v[0][0]= maxx = b;
    for (int i=1;i<n;i++) {
        v[0][i] = (1LL*a*v[0][i-1]+b)%c;
        maxx = max(maxx,v[0][i]);
    }
    while (maxx) {
       pw*=256; maxx/=256; ops++;
       fill(digit,digit+256,0);
       for (int i=0;i<n;i++) {
            digit[(v[ops%2][i]%pw)/(pw/256)]++;
       }
       for (int i=1;i<256;i++) {
            digit[i] += digit[i-1];
       }
       for (int i=255;i>=1;i--) {
            digit[i] = digit[i-1];
       }
       digit[0] = 0;
       for (int i=0;i<n;i++) {
            v[(ops+1)%2][digit[(v[ops%2][i]%pw)/(pw/256)]] = v[ops%2][i];
            digit[(v[ops%2][i]%pw)/(pw/256)]++;
       }
    }
    for (int i=0;i<n;i+=10) {
        g << v[(ops+1)%2][i] << " ";
    }
}


int main()
{
    solve();
    return 0;
}