Cod sursa(job #2591036)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 29 martie 2020 16:03:36
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;
const int dim=1<<17;
int v[10000001],n,aux[10000001];
int COUNT[256];
char next_ch()
{
    static int bp=dim;
    static char buff[dim];
    if(bp==dim)
    {
        bp=0;
        fread(buff,1,dim,stdin);
    }
    return buff[bp++];
}
void get(int &a)
{
    a=0;
    char ch;
    do
    {
        ch=next_ch();
    }
    while(ch<'0'||'9'<ch);
    do
    {
        a=a*10+ch-'0';
        ch=next_ch();
    }
    while('0'<=ch&&ch<='9');
}
void radix_sort(int val)
{
    int i;
    for(i=0; i<256; i++)
        COUNT[i]=0;
    for(i=1; i<=n; i++)
        COUNT[(v[i]>>val)&255]++;
    for(i=1; i<256; i++)
        COUNT[i]+=COUNT[i-1];
    for(i=n; i>=1; i--)
        aux[COUNT[(v[i]>>val)&255]--]=v[i];
    for(i=1; i<=n; i++)
        v[i]=aux[i];
}
int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int i,max1=0,a,b,c,val;
    cin>>n>>a>>b>>c;
    v[1]=b;
    max1=b;
    for(i=2; i<=n; i++)
    {
        v[i] = (1LL * a * v[i-1] + b) % c;
        max1=max(max1,v[i]);
    }
    for(int val=0; (1<<val)<=max1; val+=8)
        radix_sort(val);
    for(i=1; i<=n; i+=10)
        cout<<v[i]<<" ";
    return 0;
}