#include<bits/stdc++.h>

using namespace std;





int function_for_time_quantum(queue<int> ready_queue)
{

    int tot_size=ready_queue.size();

    vector<int> v_for_sort,v_for_save;


    while(!ready_queue.empty()){
        int process_burst=ready_queue.front();
        ready_queue.pop();

        v_for_save.push_back(process_burst);
        v_for_sort.push_back(process_burst);


    }

    sort(v_for_sort.begin(),v_for_sort.end());


    int median;

    if(tot_size%2==0){
        median=( v_for_sort[tot_size/2] + v_for_sort[(tot_size/2)-1] )/2.0;

    }
    else median=v_for_sort[tot_size/2];

    int diff=0;

    for(int i=1;i<v_for_sort.size();i++){
        diff+=(v_for_sort[i]-v_for_sort[i-1]);
    }



     double average_of_diff;

     if(tot_size==1) average_of_diff=diff;
     else average_of_diff=(double)diff/(tot_size-1);


    int factor=floor(average_of_diff);



    for(auto it:v_for_save){
       ready_queue.push(it);

    }

    int t=median+factor;

    return t;

}

int main()
{

    int arrival_time[105],burst_time[105],finish_time[105],response_time[105],visited[105],waiting_time[105],turn_time[105];
    int tq;

    vector<pair<int,pair<int,int>> > v;

    cout<<"Number of process, n:";

    int n;cin>>n;

    for(int i=1;i<=n;i++){
        response_time[i]=-1;
        visited[i]=0;
    }

    for(int i=1;i<=n;i++){

        cout<<"Enter the arrival time of P"<<i<<": ";
        cin>>arrival_time[i];

        cout<<"Enter the burst time of P"<<i<<": ";
        cin>>burst_time[i];


        cout<<endl;

        v.push_back({arrival_time[i],{burst_time[i],i}});

    }



    sort(v.begin(),v.end());

    queue<int> ready_queue;



    int current_time=0;
    int tot_idle_time=0;




    queue<pair<int,int> > q;


    q.push({v[0].second.first,v[0].second.second});       /// burst time , id

    ready_queue.push(v[0].second.first);
    visited[0]=1;


    current_time=v[0].first;

    cout<<"Gantt Chart: :";
    cout<<0<<" ";

    if(current_time!=0){
        cout<<"Idle "<<current_time<<" ";

        tot_idle_time+=current_time;
    }

    ///int ct=0;
    int total_completed=0;

    while(!q.empty()){

        auto x=q.front();

        int burst=x.first;
        int process_id=x.second;
        q.pop();
        ///ct++;
        if(response_time[process_id]==-1) response_time[process_id]=current_time;

        tq=function_for_time_quantum(ready_queue);

        ready_queue.pop();

        int remaining_burst_time;
        if(tq<burst){

           current_time+=tq;
           remaining_burst_time=burst-tq;

        }
        else{
           current_time+=burst;
           remaining_burst_time=0;
           finish_time[process_id]=current_time;
           total_completed++;


        }



        cout<<"P"<<process_id<<" "<<current_time<<" ";





        for(int i=0;i<n;i++){
            if(v[i].first<=current_time){
                if(visited[i]==0)
                {
                    visited[i]=1;
                    q.push({v[i].second.first,v[i].second.second});

                    ready_queue.push(v[i].second.first);

                }
            }
        }

       /// cout<<"ID2 "<<id<<" bur "<<rem<<endl;https://pastebin.pl/view/346f6894

        if(remaining_burst_time!=0){
            q.push({remaining_burst_time,process_id});

            ready_queue.push(remaining_burst_time);

        }




        if(q.empty()){
            if(total_completed!=n){
                for(int i=0;i<n;i++){
                    if(visited[i]==0)
                    {
                        visited[i]=1;
                        int arrival=v[i].first;

                        q.push({v[i].second.first,v[i].second.second});

                        ready_queue.push(v[i].second.first);



                        cout<<"Idle "<<arrival<<" ";


                        tot_idle_time+=(arrival-current_time);


                        current_time=v[i].first;


                        break;
                    }
                }

            }

        }





    }

    cout<<endl;

    ///ct=ct-1;

    double total_turn_time=0.0,total_waiting_time=0.0;


    for(int i=1;i<=n;i++){

        turn_time[i]=finish_time[i]-arrival_time[i];
        total_turn_time+=(double)finish_time[i]-arrival_time[i];

        waiting_time[i]=turn_time[i]-burst_time[i];
        total_waiting_time+=(double)turn_time[i]-burst_time[i];
    }

    for(int i=1;i<=n;i++){
        response_time[i]=response_time[i]-arrival_time[i];
    }


    for(int i=1;i<=n;i++){
        cout<<"Process: P"<<i<<" End time: "<<finish_time[i]<< " Waiting time:"<<waiting_time[i]<<" "<<"Turnaround time:"<<turn_time[i];
        cout<<" Response time "<<response_time[i];
        cout<<endl;
    }
    cout<<endl;

    cout<<"Average waiting time:"<<total_waiting_time/n<<endl;
    cout<<"Average turnaround time:"<<total_turn_time/n<<endl;
    cout<<"IDLE "<<tot_idle_time<<endl;




    ///cout<<"CONTEXT "<<ct<<endl;





}

/*

4
3
6
9
5
9
4
9
3

5
3
4
7
1
10
5
11
5
9
2

5
3
6
7
5
12
2
10
7
9
6


3
0
5
0
6
0
22


*/