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;
}


#### History

Revisions

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