Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Need help in debugging solution

Revision en2, by ROIgold, 2018-10-16 10:24:24

This problems is nice Binary Search problem, first I figured out solution by myself, then I get WA#19 and choose to watch tutorial, but it uses the same approach, after 5 more WAs at that same 19th test, I sadly watched author's shitty written solution, but as I compared it with mine, they don't differ at all, also the contest which contains that problem doesn't allow to watch people's solutions, I did substitute long long instead of int, please point me to where I'm doing something wrong.

Problem's statement
Author's solution
Tutorial, problem F
I'm very sorry, here's my code (submission):

#include <bits/stdc++.h>

#define FILE_NAME "BattleFury"

using namespace std;

typedef long long ll;

ll up(ll n, ll d) {
    return (n + d - 1) / d;
}

signed main() {
#ifdef LOCAL
    freopen(FILE_NAME".in", "r", stdin);
    freopen(FILE_NAME".out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);    
    ll n, damage, splash;
    cin >> n >> damage >> splash;
    vector<ll> creeps(n);
    for (ll& hp : creeps)
        cin >> hp;
    auto okay = [&](ll hits) {
        ll done = 0;
        for (ll hp : creeps) {
            ll left = max(0ll, hp - hits * splash);
            if (damage == splash) {
                if (left)
                    return false;
            } else done += up(left, damage - splash);
        }
        return (done <= hits);              
    };

    ll ans = -1;
    for (ll l = 1, r = (ll) 1e16; l <= r;) {
        ll hits = (l + r) / 2;
        if (okay(hits)) {
            ans = hits;
            r = hits - 1;                        
        } else l = hits + 1;    
    }
    cout << ans;
    return false;
}
Tags help, please

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English ROIgold 2018-10-16 13:44:21 3
en3 English ROIgold 2018-10-16 13:43:44 24
en2 English ROIgold 2018-10-16 10:24:24 1236 Tiny change: 'ntry/9175)\nI'm very' -> 'ntry/9175) \nI'm very'
en1 English ROIgold 2018-10-16 08:19:12 760 Initial revision (published)