Cod sursa(job #3128841)

Utilizator Dragos13Dragos Dragos13 Data 11 mai 2023 08:42:39
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
using namespace std;
void mergesort2(long long int v[],int stanga,int mijl,int dreapta) {
	int jumatate1_size = mijl - stanga + 1, jumatate2_size = dreapta - mijl;
	long long int* jumatate1 = new long long int[jumatate1_size];
	long long int* jumatate2 = new long long int[jumatate2_size];
	
	for (int i = 0; i < jumatate1_size; i++)
		jumatate1[i] = v[stanga + i];
	
	for (int i = 0; i < jumatate2_size; i++)
		jumatate2[i] = v[mijl + 1 + i];

	int jum1 = 0, jum2 = 0, index_merge = stanga;

	while (jum1 < jumatate1_size&&jum2<jumatate2_size)
	{

		if (jumatate1[jum1] <= jumatate2[jum2])
		{
			v[index_merge] = jumatate1[jum1];
			jum1++;
		}
		else
		{
			v[index_merge] = jumatate2[jum2];
			jum2++;
		}
		index_merge++;

	}

	while (jum1 < jumatate1_size) {
		v[index_merge] = jumatate1[jum1];
		jum1++;
		index_merge++;
	}

	while (jum2 < jumatate2_size) {
		v[index_merge] = jumatate2[jum2];
		jum2++;
		index_merge++;
	}
	delete[] jumatate1;
	delete[] jumatate2;
}
void mergesort1(long long int v[], int start, int final) {
	if (start >= final)
		return;
	int mijl = start + (final - start) / 2;
	mergesort1(v, start, mijl);
	mergesort1(v, mijl + 1, final);
	mergesort2(v, start, mijl, final);
	
}
int main() {
	
	ifstream in("radixsort.in");
	ofstream out("radixsort.out");
	long long int n;
	long long int a, b, c;
	in >> n>>a>>b>>c;
	cout << 1;
	long long int* v = new long long int[n];
	v[0] = b;
	for (int i = 1; i < n; i++)
		v[i] = (a * v[i - 1] + b) % c;
		
	
	mergesort1(v, 0, n - 1);
	for (int i = 0; i < n; i=i+10)
		out << v[i] << " ";
}