#include <iostream>
#include <mpi.h>
#include <cstdlib>
#include <ctime>
#include <algorithm>

int main(int argc , char ** argv){

    using namespace std;

    const int SIZE=100;
    int id, nproc,i,j=0,arranged[SIZE],a[SIZE];

    MPI_Status status;
    MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD, &nproc);
    MPI_Comm_rank(MPI_COMM_WORLD, &id) ;

    int b[nproc],place[nproc]={0};

    if(id==0){

       srand((unsigned)time(NULL));

       int number=nproc, sample, multiplier=1;

        for(i=0;i<100;i++){
            a[i]=rand()%100;
            cout<<a[i]<<" ";
        }
        cout<<endl;

        do{
           number/=10;
           multiplier*=10;
        }while(number);
            cout<<multiplier<<endl;
            sample=nproc*multiplier;

        int s[sample];

            cout<<sample<<endl;

        for(i=0;i<sample;i++){
            s[i]=a[rand()%SIZE];
            cout<<s[i]<<" ";
        }

        sort(s, s+sample);

        for(i=0;i<nproc;i++){
            b[i]=s[multiplier*(i+1)-1];
        }



        for(i=0;i<SIZE;i++){
            if(a[i]<b[id]){
             arranged[j++]=a[i];
            }
        }

        place[id]=j;

        sort(arranged, arranged+j);
        for(i=0;i<j;i++){
        }
    }

        MPI_Bcast(&b, nproc, MPI_INT, 0, MPI_COMM_WORLD);
        MPI_Bcast(&a, SIZE, MPI_INT, 0, MPI_COMM_WORLD);

    if(id!=0){

        if(id==nproc-1){
            for(i=0;i<SIZE;i++){
                 if(a[i]>=b[id]){
                    j++;
                }
            }
        }else{
            for(i=0;i<SIZE;i++){
                 if(a[i]>b[id-1] && a[i]<=b[id]){
                    j++;
                 }
            }
        }

        MPI_Send(&id,1,MPI_INT,0,123,MPI_COMM_WORLD);
        MPI_Send(&j,1,MPI_INT,0,234,MPI_COMM_WORLD);

        int slave[j];
        j=0;

        if(id==nproc-1){
            for(i=0;i<SIZE;i++){
                if(a[i]>=b[id]){
                    slave[j++]=a[i];
                }
            }

        }else{
            for(i=0;i<SIZE;i++){
                if(a[i]>b[id-1] && a[i]<=b[id]){
                    slave[j++]=a[i];
                }
            }
        }
        sort(slave,slave+j);

        MPI_Send(&id,1,MPI_INT,0,123,MPI_COMM_WORLD);
        MPI_Send(&slave,j,MPI_INT,0,345,MPI_COMM_WORLD);

    }else{

        for(i=1;i<nproc;i++){
            MPI_Recv(&id, 1, MPI_INT, MPI_ANY_SOURCE, 123, MPI_COMM_WORLD, &status);
            MPI_Recv(&place[id], 1, MPI_INT, id, 234, MPI_COMM_WORLD, &status);
        }

        for(i=0;i<nproc;i++) {b[i]=0;}

        for(i=0;i<nproc;i++){
            for(j=0;j<i;j++){
                b[i]+=place[j];
            }
        }

        for(i=1;i<nproc;i++){
            MPI_Recv(&id, 1, MPI_INT, MPI_ANY_SOURCE, 123, MPI_COMM_WORLD, &status);
            MPI_Recv(&arranged+b[id], place[id], MPI_INT, id, 345, MPI_COMM_WORLD, &status);
        }

        for(i=0;i<SIZE;i++){
            cout<<arranged[i]<<" ";
        }
    }

    MPI_Finalize();
}