bmp_lb, C++ (gcc) - rextester

bmp_lb

// Load balancing
#include<bits/stdc++.h>
using namespace std;

int main(){
    
    long long int n,m; // grid size - n*m
    long long int x1,y1,x2,y2; // region area points
    long long int nc,nxf,nyf,nf,nxc,nyc;
    long long int factor;
    long long int total_works = 0;
    long long int p;
    
    cin>>n>>m;
    cin>>x1>>y1>>x2>>y2>>factor;
    cin>>p;
    
    nxf = (x2-x1+1)*factor;
    nyf = (y2-y1+1)*factor;
    nf = nxf*nyf;
    
    nxc = n;
    nyc = m;
    nc = nxc*nyc;
    
    total_works = nc + (factor-1)*nf;
    
    cout << nc << endl;
    cout << total_works << endl; 
    
    long long int pre_work[nxc+1];
    pre_work[0] = 0;
    for(int i=1;i<=nxc;i++){
        pre_work[i] = pre_work[i-1] + nyc;
        if(i>=x1 && i<=x2){
            pre_work[i] += (factor-1)*nyf*factor;
        }
    }
    cout<<pre_work[nxc]<<endl;
    
    long long int i,low = 1;
    long long int high = total_works;
    long long int mid;
    long long int pre;
    long long int ans = total_works;
    pair<int,int> dist[p+1];
    int work[p+1];
    
    while(low<=high){
        mid = (high + low)/2;
        pre = 0;        
        for(i=1;i<=p;i++){
            int idx = upper_bound(pre_work,pre_work+nxc+1,mid+pre)-pre_work;
            pre = pre_work[idx-1];
        }
        if(pre >= total_works){
            high = mid - 1;
            ans = min(ans,mid);
        }else{
            low = mid + 1;
        }
    }
    
    int lastidx = 0;
    for(i=1;i<=p;i++){
       int idx = upper_bound(pre_work,pre_work+nxc+1,ans+pre_work[lastidx])-pre_work;
       dist[i] = {lastidx+1,idx-1};
       work[i] = pre_work[idx-1] - pre_work[lastidx];
       lastidx = idx - 1;
    }
    
    cout << "Maximum work to single processor :- "<<ans << endl;
    cout << " Processor \t start point \t end point \t tasks " <<endl;
    for(int i=1;i<=p;i++){
        cout << "Processor-"<<i<<"\t\t"<<dist[i].first<<"\t\t"<<dist[i].second<<"\t"<<work[i]<<endl;
    }
    /*int regions;
    cin>>regions;
    
    for(int i=0;i<regions;i++){
        cin>>x1>>y1>>x2>>y2>>fx>>fy;
        total_works += 
    }*/
    return 0;
}


run \| edit \| history \| help	0