Problem Link:
Practice
Contest
Author: Pratik Suryawanshi
Editorialist: Pratik Suryawanshi
DIFFICULTY:
Moderate
PREREQUISITES:
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 ¢res = 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;
}