i think there is some mistake in while loop and because of which this code is taking more than 5 seconds. an you help me figure out where i went wrong with this code.
#include <iostream>
#include <stdio.h>
#include <set>
#include <iterator>
using namespace std;
// it checks whether there is a value present in multiset in the range [x,2x]
long int check_bound(multiset S, long int X)
{
multiset<long int>::iterator it1, it2;
it1 = S.lower_bound(X);
it2 = S.upper_bound(2 * X);
long int ans;
if (it1 != it2)
{
--it2;
ans = *(it2);
}
else
{
ans = -1;
}
return ans;
}
int main()
{
// your code goes here
int T;
cin >> T;
for (int k = 0; k < T; k++)
{
int N;
long int x;
long int temp;
long long int days = 0;
short int honesty = 0;
multiset<long int> s;
multiset<long int>::iterator itr, itr1, itr2;
scanf("%d", &N);
scanf("%ld", &x);
for (int i = 0; i < N; i++)
{
scanf("%ld", &temp);
s.insert(temp);
} // adding all population entries into multiset
while (honesty != 1)
{
// <A> // when set is empty i.e no countries left to cure
if (s.size() == 0)
{
honesty = 1;
}
// <B> // set has some ocuntris to cure
else
{
itr = s.end();
--itr;
// <0>
if (x >= *(itr))
{ // if X is greter than country with highest population
days = N; // then it needs just N days
honesty = 1;
}
// <1>
else
{
// <1.1>
if (days == 0) // x is less than largerst population on first day
{ // so using that country to grow number of cures
temp = *itr;
s.erase(itr);
if ((temp - x) * 2 >= temp)
{
s.insert(temp);
}
else
{
s.insert((temp - x) * 2);
}
}
// <1.2>
else
{
itr = s.end();
--itr;
long int z;
z = check_bound(s, x); // stores most populous country value in range [x,2x]
// <2>
if (z != -1)
{
// <2.1>
if (z == *itr)
{ // that is if largest pop... falls in range of [x, 2x]
days = days + s.size(); // required days is equal to number of countries in set currently
honesty = true;
}
// <2.2>
else
{
x = z; // as z no. of cures will be used this day
s.erase(itr); // as entire population will get cured
days++;
honesty = false;
}
} // end of <2>
// <3> when nothing found in set in the range [x,2x]
else {
// <3.1>
if ( *(itr) > 2*x) { // highest popu... country in set is greater than 2 times of x (cures used in prev day)
temp = *(itr) ; // storing that popula... in temp var
s.erase(itr) ;
x = x*2 ; // as we will use 2*x cures today to treat highest popul... country
if ( (temp - x)*2 > temp ){
s.insert(temp) ;
}
else {
s.insert( (temp -x)*2 ) ;
}
days++ ;
honesty = 0 ;
}
// <3.2>
else { // highst pop... is either equal or less than 2*x
days = days + s.size() ;
honesty = 1 ;
}
} // end of <3>
}
} // end of <1>
} // end of <B>
} // end of while loop
cout<<days<<endl;
} // TEstcase loop ends here
return 0;
}