Cod sursa(job #2805619)

Utilizator victorzarzuZarzu Victor victorzarzu Data 21 noiembrie 2021 15:47:54
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>


using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int a[10000005];
int n, x, y, z;

#define total_size sizeof(a[0])
#define radix 0xff
#define radix_size 8
#define get_byte(x) (x >> (8 * byte) & radix)

void read()
{
  f>>n>>x>>y>>z;
  f.close();
}

void radixsort(int *a1, int *a2, int byte)
{
  int counter[1 << radix_size];
  int index[1 << radix_size];

  memset(counter, 0, sizeof(counter));

  for(int i = 1;i <= n;++i)
    ++counter[get_byte(a1[i])];
  
  index[0] = 1;
  for(int i = 1;i < (1 << radix_size);++i)
    index[i] = index[i - 1] + counter[i - 1];
  
  for(int i = 1;i <= n;++i)
    a2[index[get_byte(a1[i])]++] = a1[i];
}

void solve()
{
  int *tmp = new int[n + 1];

  a[1] = y % z;
  for(int i = 2;i <= n;++i)
    a[i] = (long long)((1LL * x * a[i - 1]) % z + y) % z;     

  for(int i = 0;i < total_size;++i)
    if(i & 1)
      radixsort(tmp, a, i);
    else
      radixsort(a, tmp, i);

  for(int i = 1;i <= n;i += 10) 
    g<<a[i]<<" ";
  g.close();
}

int main()
{
  read();
  solve();
  return 0;
}