Cod sursa(job #3311685)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 23 septembrie 2025 18:18:35
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
//#define TESTS

#define x first
#define y second
#define pii pair<int,int>
#define veci vector<int>
#define vecp vector<pii>
#define all(x) x.begin(), x.end()
#define pb(x,y) x.push_back(y)

const int maxn = 1e7+5;

int n,a,b,c;
int v[maxn];
int buf[maxn];

void merge_sort(int st, int dr)
{
	if(st==dr) return;

	int mid=(st+dr)/2;

	merge_sort(st, mid);
	merge_sort(mid+1, dr);

	int pst=st;
	int pdr=mid+1;
	int pbuf=st;
	
	while(pst<= mid && pdr <= dr)
	{
		if(v[pst] < v[pdr])
		{
			buf[pbuf++] = v[pst++];
		}
		else
		{
			buf[pbuf++] = v[pdr++];
		}
	}

	while(pst<=mid) buf[pbuf++] = v[pst++];
	while(pdr<=dr) buf[pbuf++] = v[pdr++];


	for(int i=st;i<=dr;i++)
	{
		v[i]=buf[i];
	}
}


void solve()
{
	cin>>n>>a>>b>>c;
	v[1]= b;

	for(int i=2;i<=n;i++)
	{
		v[i]= (a*v[i-1]+b) % c;
	}

	merge_sort(1, n);

	for(int i=1;i<=n;i+=10) cout<<v[i]<<' ';
	cout<<'\n';
}

int main()
{
	#ifndef LOCAL
		#define fname "radixsort"
		freopen(fname".in","r", stdin);
		freopen(fname".out","w",stdout);
	#endif

	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int t=1;

	#ifdef TESTS
		cin>>t;
	#endif
	while(t--)
	{
		solve();
	}
	return 0;
}