PROBLEM LINK: Find Least immune | CodeChef
Problem Code: Find Least immune | CodeChef
Practice: CodeChef | Competitive Programming | Participate & Learn | CodeChef
Contest : Carnival Finale Coding Competition | CodeChef
Author: Codechef Adgitm Chapter :
ishayadav181 | CodeChef User Profile for Isha Yadav | CodeChef
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
DIFFICULTY:
Easy-Medium
PROBLEM:
Amid second wave of Covid-19, NN people are trying to get vaccinated. The clinic can vaccinate 11 person per minute and at most MM people can wait in the clinic maintaining social distancing. As everyone is very serious about maintaining social distancing rules, only MM people go in the clinic at a time.
After first person gets vaccinated, he moves out and M+1thM+1th person goes in, after second person gets vaccinated , he moves out and M+2thM+2th person goes in. Similarly everyone gets vaccinated.
As social distancing alone is not sufficient to prevent infection, we need to take more precautions like wearing a mask and sanitizing hands etc. For every person from 11 to NN we are given p[ ii ] , number of precautions the person is taking to be safe.
If the clinic has exactly MM people, then the person taking least precautions will get infected.
Find the number of times each person will get infected.
You are given TT testcases. First line of each testcase contains two integers NN and MM second line of each testcase contains N integers , ithith integer denoting precautions taken by ithith person
For each testcase in new line print N space separated integers, where ithith integer is equal to the number of times the ithith person will get infected.
EXPLANATION:
Use push and pop concept.
SOLUTION:
C++:
#include<bits/stdc++.h>
using namespace std;
void sliding(int a[],int n,int k,int temp[])
{
dequeq(k);
int i;
for(i=0;i<k;i++)
{
while(!q.empty()&&a[i]<a[q.back()])
{
q.pop_back();
}
q.push_back(i);
}
for(;i<n;i++)
{
temp[q.front()]++;
while((!q.empty())&&q.front()<=i-k)
q.pop_front();
while((!q.empty())&&a[i]<a[q.back()])
q.pop_back();
q.push_back(i);
}
temp[q.front()]++;
}
int main(){
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int a[n]={0};
sliding(arr,n,k,a);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
}