Pagini recente » Cod sursa (job #926385) | Cod sursa (job #452610) | Cod sursa (job #1978691) | Cod sursa (job #770578) | Cod sursa (job #2930942)
#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>
#define NMAX 2003
#define MOD 1000000007
using namespace std;
int n,a,b,c;
queue<long long int> bucket[10];
FILE* fin, * fout;
int main()
{
fin = fopen("radixsort.in", "r");
fout = fopen("radixsort.out", "w");
fscanf(fin, "%d %d %d %d", &n, &a, &b, &c);
long long int prec = b;
bucket[prec % 10].push(prec);
for (int i = 2; i <= n; i++)
{
long long int x = ((long long int)a * prec + b)%c;
bucket[x % 10].push(x);
prec = x;
}
//fac un counting sort pe astea
//Practic fac mereu o sortare dupa cifra de pe pozitia x/p
//Si pun sortarile astea un bucket-uri
//Dar e important cand imi refac vectorul sa imi scot elementele
//in aceeasi ordine in care le-am bagat
//Pentru ca asa se pastreaza sortate in bucket
long long int p = 10;
while (1)
{
//imi refac vectorul initial
vector<long long int>sortat;
for (int i = 0; i <= 9; i++)
{
while (!bucket[i].empty())
{
sortat.push_back(bucket[i].front());
bucket[i].pop();
}
}
//acuma sortez frumos dupa urmatoarea cifra semnificativa
bool amMaiMare = false;
for (int i = 0; i < sortat.size(); i++)
{
int poz = (sortat[i] / p) % 10;
if (sortat[i] > p)
{
amMaiMare = true;
}
bucket[poz].push(sortat[i]);
}
if (!amMaiMare)
{
//am terminat, ma opresc
break;
}
p = p * 10;
}
vector<long long int>sortat;
for (int i = 0; i <= 9; i++)
{
while (!bucket[i].empty())
{
sortat.push_back(bucket[i].front());
bucket[i].pop();
}
}
for (int i = 0; i < sortat.size(); i += 10)
{
fprintf(fout, "%d ", sortat[i]);
}
return 0;
}