# COVIDCENTRE - EDITORIAL

Practice
Contest

Author: Pratik Suryawanshi

Editorialist: Pratik Suryawanshi

Moderate

Binary Search

# PROBLEM:

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 )

# EXPLANATION:

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

# SOLUTIONS:

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;
#include<bits/stdc++.h>
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){
vacant_centres.insert(centre);
}
to_discharge.erase(it);
}
}
int get_vacant_centre(int patient_index){
auto avaliable_centre_it = vacant_centres.lower_bound(patient_index%m);
if(avaliable_centre_it==vacant_centres.end())
avaliable_centre_it==vacant_centres.begin();
return *avaliable_centre_it;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
freopen(“errorf.txt” , “w” , stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

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){
vacant_centres.insert(i);
}
for(auto &timing : timings){
int arrival_day=timing.first;
int treatment_days=timing.second;
discharge_patients_untill_day(arrival_day);

if(vacant_centres.size()==0) continue;

int patient_index=&timing - &timings[0];
int avaliable_centre = get_vacant_centre(patient_index);

to_discharge[arrival_day+treatment_days].pb(avaliable_centre);
treated_count[avaliable_centre]++;
vacant_centres.erase(avaliable_centre);
}
for(int i=0;i<m;++i){
cout << treated_count[i] << " ";
}
return 0;

}