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

using namespace std;

const long long SIZE=100;
int a[SIZE];

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

    int id, nproc;
    MPI_Status status;
    MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD, &nproc);
    MPI_Comm_rank(MPI_COMM_WORLD, &id) ;
    int i, b[nproc],j=0, order[SIZE], lenght[nproc]={0};;

    if(id==0){
       srand(time(NULL));

       int meret=nproc, sample, tmp=1;

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

        int s[sample];

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

        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[tmp*(i+1)-1];
            cout<<b[i]<<" ";
        }


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

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

        lenght[id]=j;

        sort(order, order+j);
        for(i=0;i<j;i++){
            cout<<order[i]<<" ";
        }
    }

    if(id!=0){
        MPI_Recv(&b, nproc, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
        MPI_Recv(&a, SIZE, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);

        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]; j++;
                }
            }

        }else{
            for(i=0;i<SIZE;i++){
                if(a[i]>b[id-1] && a[i]<=b[id]){
                    slave[j]=a[i]; j++;
                }
            }
        }
        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(&lenght[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]+=lenght[j];
            }
        }

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

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

    MPI_Finalize();
}