1 / 3
Mar 8

Please can anyone explain what is wrong with this code? Even providing a test case where this code fails would be appreciated.

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

double eps = 1e-5;

bool isDivPossible(vector v, ll f, double m)
{
ll sz = v.size();
auto begIt = v.begin();
while(f)
{
auto it = lower_bound(begIt, v.end(), m);
if(it == v.end())
return false;

    ll ind = distance(v.begin(), it);

    for( ; ind < sz; ind++)
    {
        v[ind] -= m;
        f--;

        if(f == 0)
            break;
    }

    begIt = it;
}

return true;

}

int main()
{
ll t;
cin >> t;

while(t--)
{
    ll n, f;
    cin >> n >> f;
    f++;

    vector <double> v;
    for(ll i = 0; i < n; i++)
    {
        double inp;
        cin >> inp;

        v.push_back(inp * inp * M_PI);
    }

    sort(v.begin(), v.end());

    double lo = M_PI, hi = 1e8 * M_PI;
    while(hi - lo > eps)
    {
        double mid = (lo + hi) / 2;

        if(isDivPossible(v, f, mid))
            lo = mid;
        else
            hi = mid - eps;
    }

    if(isDivPossible(v, f, hi))
        cout << fixed << setprecision(4) << hi << '\n';
    else
        cout << fixed << setprecision(4) << lo << '\n';
}

}

Thanks in advance.

  • created

    Mar 8
  • last reply

    Mar 8
  • 2

    replies

  • 100

    views

  • 2

    users

  • 1

    like

  • 1

    link

Try these

3
1 10000
1
1 10000
3
1 10000
4

Thanks a lot. Found the problem. I set the lower bound wrong. After correcting it, now the answer is accepted.:grin: