#include<mpi/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("\nSorted incorrectly\n");
			return;
		}
	}
	printf("\nSorted 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);

	}

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

    if (rank == 0)
    {
        for (int i = 1; i < nProcesses; i++)
        {
            MPI_Send(&v_size, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
            MPI_Send(v, v_size, MPI_INT, i, 0, MPI_COMM_WORLD);
        }
        int step = v_size / nProcesses;
        int * aux = (int*) calloc(v_size, sizeof(int));
        int * vecCopy = (int*) malloc(v_size * sizeof(int));
        printf("Eu, procesul %d, voi prelucra intre %d si %d\n", rank, 0, step-1);
        for (int i = 0 ; i < step; i++)
        {
            for (int j = 0; j < v_size; j++)
                if (v[i] > v[j])
                    aux[i]++;
            vecCopy[aux[i]] = v[i];
        }
        displayVector(vecCopy, v_size);
        for (int i = 0 ; i < step; i++)
            printf("Rank %d : poz din v : %d, pozitia corecta : %d\n", rank, v[i], aux[i]);
        for (int i = 1 ; i < nProcesses-1; i++)
        {
            MPI_Recv(aux, step, MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            displayVector(aux, step);
            for (int j = 0 ; j < step; j++)
                vecCopy[aux[j]] = v[i*step + j];
            printf("Dupa pasul %i\n", i);
            displayVector(vecCopy, v_size);
        }
        MPI_Recv(aux, v_size - ((nProcesses-1) * step), MPI_INT, nProcesses-1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        displayVector(aux, v_size - ((nProcesses-1) * step));

        for (int j = 0 ; j < v_size - ((nProcesses-1) * step); j++)
            vecCopy[aux[j]] = v[(nProcesses-1)*step+j];
        printf("Dupa pasul %i\n", nProcesses-1);
        displayVector(vecCopy, v_size);
        for (int i = 0 ; i < v_size ; i++)
        {
            v[i] = vecCopy[i];
            printf("%d ", v[i]);
        }
    }
    else
    {
        MPI_Recv(&v_size, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        v = (int*)malloc(sizeof(int)*v_size);
        MPI_Recv(v, v_size, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        int step = v_size / nProcesses;
        if ( rank < nProcesses -1 )
        {
            int step = v_size / nProcesses;
            int * aux = (int*) calloc(v_size, sizeof(int));
            printf("Eu, procesul %d, voi prelucra intre %d si %d\n", rank, step*rank, step*(rank+1)-1);
            for (int i = step * rank ; i < step * (rank+1); i++)
                for (int j = 0 ; j < v_size; j++)
                    if (v[i] > v[j])
                        aux[i]++;
            for (int i = step * rank ; i < step * (rank+1); i++)
                printf("Rank %d : poz din v : %d, pozitia corecta : %d\n", rank, v[i], aux[i]);
            printf("Eu, procesul %d, trimit inapoi intre %d si %d\n", rank, step*rank, step*(rank+1)-1);
            MPI_Send(&aux[step*rank], step, MPI_INT, 0, 0, MPI_COMM_WORLD);
        }
        else
        {
                int step = v_size / nProcesses;
                int * aux = (int*) calloc(v_size, sizeof(int));
                printf("Eu, procesul %d, voi prelucra intre %d si %d\n", rank, step*rank, v_size);
                for (int i = step * rank ; i < v_size; i++)
                    for (int j = 0 ; j < v_size; j++)
                        if (v[i] > v[j])
                            aux[i]++;
            for (int i = step * rank ; i < v_size; i++)
                printf("Rank %d : poz din v : %d, pozitia corecta : %d\n", rank, v[i], aux[i]);
            printf("Eu, procesul %d, trimit inapoi intre %d si %d\n", rank, step*rank, step*(rank+1)-1);
            MPI_Send(&aux[step*rank], v_size - step * rank, MPI_INT, 0, 0, MPI_COMM_WORLD);
        }
    }
	// DO NOT MODIFY
	if(rank == 0) {
		// displayVector(v, v_size);
		compareVectors(v, vQSort, v_size);
	}

	MPI_Finalize();
	return 0;
}