Problem Link:

Author: Pratik Suryawanshi

Editorialist: Pratik Suryawanshi




Binary Search


There are M covid centres denoted by IDs 0 to M-1 located on a circular path
( centre 1 is right to centre 0, centre 2 is right to centre 1, …. centre 0 is
right to centre M-1). Each centre can treat only one patient at a time. There ar N
patients and two arrays, arrival and treatment of length N is given. Arrival denotes that
ith patient arrives to (i%m)th centre on arrival[i]th day. If centre is occupied,
then they try getting admitted to the closest vacant centre clockwise right to (i%m)th
centre. IF no centrre is vaccant . then the patient leaves, Once admitted in a centre ,
the patients gets treated for treatment[i] days there and then leaves.
output M values in which ith value denotes the number of patients treated by ith
covid centre in total . Note :- arrival[i] and treatment[i] is the ith element of the array
. arrival and treatment respectively. ( 0 indexing is followed )


The first patient arrives on day 1 and as the 0th centre (because i%m = 0) is vacant, they occupy the 0th centre and will leave on (1+6) = 7th day.

The second patient arrives oon day 3 and as 1st centre ( because 1%3 = 1) is vacant , they occupy the 2nd centre and will leave on (3+10) = 13th day,

The third patient arrives oon day 6 and as 2nd centre ( because 2%3 = 1) is vacant , they occupy the 2nd centre and will leave on (6+1) = 7th day,

The fourth patient arrives oon day 7 and as 0th centre ( because 3%3 = 0) is not vacant , and next clockwise vacant centres is 2nd centre, they occupy the 2nd centre and will leave on (7+10) = 17th day.

The fifth and last patient arrives on day 10 and as 1st centre (because 4%3 = 1) is not vacant and next clockwise vacant centre is 0th , they occupy the 0th centre and will leave on (10+1) = 11th day.

Centre 0 was visited by : first and fifth patient

centre 1 was visited by : second patient

centre 2 was visited by : third and fourth patient


Setter's Solution

#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)
#pragma GCC optimization(“unroll-loops”)
#include <bits/stdc++.h>
using namespace std;
#define tc ll t sc cin >> t sc while (t–)
#define ff first
#define vp vector<pair<ll,ll>>
#define sc ;
#define ss second
#define srt sort
#define endl ‘\n’
#define pb push_back
#define pp pop_back
#define mp make_pair
#define modulo 1e9+7
#define ll long long int
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define INF 1001001001
const long double pi = 3.141592653;

typedef unsigned int ui;
typedef unsigned long long int ul;
using namespace std;

int n,m;
set vacant_centres;
map<int,vector > to_discharge;

void discharge_patients_untill_day(int day){
for(auto it=to_discharge.begin(); it != to_discharge.end(); ++it){
int discharge_day = it->first;
auto &centres = it->second;
if(day<discharge_day) break;
for(auto centre : centres){
int get_vacant_centre(int patient_index){
auto avaliable_centre_it = vacant_centres.lower_bound(patient_index%m);
return *avaliable_centre_it;
int main()
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
freopen(“errorf.txt” , “w” , stderr);

cin >> n >> m;
vector<pair<int,int> > timings(n);
vector<int> treated_count(m,0);

for(int i=0;i<n;++i){
    cin >> timings[i].first;
for(int i=0;i<n;++i){
    cin >> timings[i].second;

srt(timings.begin(), timings.end());

for(int i=0;i<m;++i){
for(auto &timing : timings){
    int arrival_day=timing.first;
    int treatment_days=timing.second;
    if(vacant_centres.size()==0) continue;
    int patient_index=&timing - &timings[0];
    int avaliable_centre = get_vacant_centre(patient_index);
for(int i=0;i<m;++i){
    cout << treated_count[i] << " ";
return 0;