Cod sursa(job #2931418)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 31 octombrie 2022 09:39:26
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#pragma GCC optimize("O1")

#pragma GCC optimize("O2")

#pragma GCC optimize("O3")

#pragma GCC optimize("O4")

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

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

long long n,A,B,C;
int a[10000005],b[2][10000005];

int main()
{
    in >> n >> A >> B >> C;
    a[0] = B;
    for (int i = 1; i < n; i++)
        a[i] = 1ll * (A * a[i - 1] + B) % C;
    int p256 = -1;
	int s[2] = {0,0};
    for (int q = 0; q < 31; q++)
    {
        p256++;
        for (int i = 0; i < n; i++)
        {
			int pozz = (a[i] >> p256) & 1;
			b[pozz][s[pozz]++] = a[i];
		 }
		 int act = 0;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < s[i]; j++)
                a[act++] = b[i][j];
            s[i] = 0;
        }
    }
    for (int i = 0; i < n; i += 10)
        out << a[i] << ' ';
    return 0;
}