Mai intai trebuie sa te autentifici.
Cod sursa(job #1841902)
Utilizator | Data | 6 ianuarie 2017 11:28:10 | |
---|---|---|---|
Problema | Radix Sort | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.37 kb |
#include <cstdio>
#include <cstring>
#define BITS 255
using namespace std;
FILE *f, *g;
int n, a, b, c;
int v[10000003];
void readFile()
{
f = fopen("radixsort.in", "r");
fscanf(f, "%d%d%d%d", &n, &a, &b, &c);
fclose(f);
}
void getNumbers()
{
int i;
v[1] = b;
for(i = 2; i <= n; i ++)
v[i] = (1LL * a * v[i - 1] % c + b) % c;
}
void radixSort()
{
int *temp = new int[n];
int *pozv[2] = {v, temp};
int *aux;
int index[BITS + 10];
int frec[BITS + 10];
int bits, i;
for(bits = 0; bits < 32; bits += 8)
{
memset(frec, 0, sizeof(frec));
for(i = 1; i <= n; i ++)
frec[(pozv[0][i] >> bits) & BITS] ++;
index[0] = 1;
for(i = 1; i <= BITS; i ++)
index[i] = index[i - 1] + frec[i - 1];
for(i = 1; i <= n; i ++)
pozv[1][index[(pozv[0][i] >> bits) & BITS] ++] = pozv[0][i];
aux = pozv[0];
pozv[0] = pozv[1];
pozv[1] = aux;
}
}
void solve()
{
getNumbers();
radixSort();
}
void printFile()
{
g = fopen("radixsort.out", "w");
int i;
for(i = 1; i <= n; i += 10)
fprintf(g, "%d ", v[i]);
fprintf(g, "\n");
fclose(g);
}
int main()
{
readFile();
solve();
printFile();
return 0;
}