Блог пользователя cschill

Unable to find the reason for the wrong Answer
Автор cschill, история, 12 месяцев назад, По-английски

I was trying this problem — https://mirror.codeforces.com/problemset/problem/348/A

Its a simple binary search problem but it shows wrong answer — https://mirror.codeforces.com/contest/348/submission/235257891

I changed my high to 1e14 from 1e16 and its accepted. I am unable to understand what was the reason behind the error.... please let me know if anyone have a clue about it :))

Thanks

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

This is due to integer overflow, as you might have guessed.

The variable sum in the function check will overflow as it can be at max n * (x — 1), if all elements in the array are 1.

Since n can go up to 1e5 and x is (1e16) / 2 = 2e15 in the first iteration, n * (x — 1) is about 2e20 which is beyond the 64 bit integer limit

→ Ответить