#include<mpi.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

void compareVectors(int * a, int * b, int n) {
	// DO NOT MODIFY
	int i;
	for(i = 0; i < n; i++) {
		if(a[i]!=b[i]) {
			printf("Sorted incorrectly\n");
			return;
		}
	}
	printf("Sorted correctly\n");
}

void displayVector(int * v, int n) {
	// DO NOT MODIFY
	int i;
	for(i = 0; i < n; i++) {
		printf("%d ", v[i]);
	}
	printf("\n");
}

int cmp(const void *a, const void *b) {
	// DO NOT MODIFY
	int A = *(int*)a;
	int B = *(int*)b;
	return A-B;
}

int main(int argc, char * argv[]) {
	int rank;
	int nProcesses;
	MPI_Init(&argc, &argv);

	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &nProcesses);
	printf("Hello from %i/%i\n", rank, nProcesses);

	int *v, *vQSort;
	int v_size;

	if(rank==0) { // This code is run by a single process
		int i;

		// read the vector v
		// DO NOT MODIFY
		scanf("%d", &v_size);

		// Alocate memory
		vQSort = (int*)malloc(sizeof(int)*v_size);
		v = (int*)malloc(sizeof(int)*v_size);

		for(i = 0; i < v_size; i++)
			scanf("%d", &v[i]);

		// make copy to check it against qsort
		// DO NOT MODIFY
		for(i = 0; i < v_size; i++)
			vQSort[i] = v[i];

		qsort(vQSort, v_size, sizeof(int), cmp);
		int count = v_size / nProcesses;
		//printf("eu voi avea de la 0 la %d\n", count);
		int index = count;
		for (i = 1; i < nProcesses; i++) {
			if (i != nProcesses -1) {
				//printf("Trimit de la index %d %d elemente\n", index, count);
				MPI_Send(&index, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
				MPI_Send(&count, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
				MPI_Send(&v_size, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
				MPI_Send(v, v_size, MPI_INT, i, 1, MPI_COMM_WORLD);
				index += count;
			}
			else {
				count = v_size - ((v_size / nProcesses) * (nProcesses-1));
				//printf("*Trimit de la index %d, %d elemente\n", index, count);
				MPI_Send(&index, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
				MPI_Send(&count, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
				MPI_Send(&v_size, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
				MPI_Send(v, v_size, MPI_INT, i, 1, MPI_COMM_WORLD);
				index += count;
			}
		}

	}

	else {
		int count, size, index = 0;
		MPI_Recv(&index, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		MPI_Recv(&count, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		MPI_Recv(&size, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		int* myvec = (int*) malloc(size*sizeof(int));
		MPI_Recv(myvec, size, MPI_INT, 0, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		printf("rank %d, myvec: ", rank);
		int i;
		for (i = 0; i < size; i++) {
			printf("%d ", myvec[i]);
		}
		printf("SUnt rank %d si procesez de la %d pana la %d\n", index, coun

		printf("\n");
		//printf("Sunt in ranku %d si primesc countul %d\n", rank, count);
	}

	// HERE YOU DO YOUR MAGIC, SO RANK == 0 to have the vector
	// sorted at the end.



	// DO NOT MODIFY
	if(rank == 0) {
		// displayVector(v, v_size);
		compareVectors(v, vQSort, v_size);
	}

	MPI_Finalize();
	return 0;
}