Cod sursa(job #2374994)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 7 martie 2019 21:41:24
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int n, a, b, c;
int gr1[10000002], gr2[10000002];
bool gr[10000002];
int main()
{
    f >> n >> a >> b >> c;
    gr1[1] = b;
    for(int i = 2; i <= n; ++i)
    {
        long long z = (1LL * a * gr1[i-1] + b) % c;
        gr1[i] = z;
    }
    gr[n+1] = 1;
    int bg = 1;
    for(int i = 30; i >= 0; --i)
    {
        while(gr[bg + 1])
            ++bg;
        int st = bg;
        int np = 0;
        while(st <= n)
        {
            int dr = st;
            while(!gr[dr+1])
                ++dr;
            for(int j = st; j <= dr; ++j)
                if(!(gr1[j] & (1<<i)))
                    gr2[++np] = gr1[j];
            gr[np+1] = 1;
            for(int j = st; j <= dr; ++j)
                if((gr1[j] & (1<<i)))
                    gr2[++np] = gr1[j];
            st = dr + 1;
        }
        memcpy(gr1, gr2, sizeof(gr2));
    }
    for(int j = 1; j <= n; j += 10)
        g << gr1[j] << " ";
    return 0;
}