BOOKS1-Copying Books

Copying Books

Given below c++ code is for books1 spoj or cpoying books spoj.

Hint:-Simple Binary Search implementation.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 24 October 2015 (Saturday) 10:28
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
bool check(int A , vector<int> &v , ull mid){
    int  n = v.size() , i = 0 , tot = 1;
    ull count = 0;
    while(i < n)
    {
        if((long long)v[i] > mid)
            return false;
        if(count + (long long )v[i] > mid){
            tot++;
            count = 0;
        }
        if(count <= mid){
            count += (long long)v[i];
            i++;
        }
    }
    if(tot <= A)
        return true;
    return false;
}
bool print(int pos , int k ,vector<int> &v , ull mid){
    ull count = 0;
    int pos_till = -1;
    for(int i = pos ; i>= 0 ; i--){
        if(count + v[i] > mid || i == k-2){
            print(i , k-1  , v , mid);
            pos_till = i;
            break;
        }
        count += v[i];
    }
    if(pos_till >= 0)
        printf("/ ");
    for(int i = pos_till +1 ; i<= pos ; i++)
        printf("%d ", v[i]);
}
ull binary_search(vector<int> &v , int A){
    ull low = 1 , high = LLONG_MAX , mid , ans = LLONG_MAX;
    while(low < high){
        mid = (low + high)>>1;
        if(check(A , v , mid)){
            ans = min(ans , mid);
            high = mid;
        } else
            low = mid+1;
    }
    return ans;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int m , k;
        scanf("%d%d",&m,&k);
        vector<int> v(m);
        for(int i = 0 ; i < m ; i ++){
            scanf("%d",&v[i]);
        }
        v.pb(0);
        ull ans = binary_search(v , k);
        print(v.size() - 2 , k , v , ans);
        printf("\n");
    }
    return 0;
}