As the title, 1e18 + 1 == 1e18 in C++.
This is because the double type stores the first 53 binary bits of a number. So the number 1 will be ignored.
And most of submissions which fst on test 13 of problem C of edu round 187 are for this reason.
UPD: I collected some suggestions from the comments:
- Use
1000000000000000001(I do not suggest it because it is prone to errors.) - Use
(long long)(1e18) + 1 - Use
1e18L + 1 - Use
1'000'000'000'000'000'001LL
Auto comment: topic has been updated by XiangXunyi (previous revision, new revision, compare).
f*ck this shit
I got wrong for this :(
Just use LLONG_MAX, it's in the c++ standard and expressive!
reference
Then inf + inf leads to overflow. I don't like to assign more than 3e18 to inf for that reason.
i usually use
LLONG_MAX/4so that it is >2e18 while inf+inf is still in long long range. for int i would useINT_MAX/2although it is a strange habit but it avoids problems most of the time
laugh as never use expressions like that.i only use 100000000... despite that the work of counting zeros is a bit annoying
u can type 1'000'000'000 instead
hi! i think using implicit conversion is a good enough fix for this i.e. using something like: -
i used the above mentioned declaration for my binary search bounds, and it AC'ed without any issues.
although i do believe the best way to avoid such issues is to use integer literals: -
Why is it that we should use 1000000000000000000LL instead of 1e18, really curious as I have zero idea?
essentially because they represent different data types, 1e18 is a double whereas the first one's an integer literal.
u can just force it back to long long to avoid this problem, like this
const long long INF = (long long) 1e18;There is
1e18lin g++yeah, i use this only most of times with binary search
你说的很对！
I hate this type of bug. That's I always initialize long long with a loop to make sure the value reach exactly the correct limit. For example, to initialize with 1e18 + 1 it suffices to do:
Note the optimization that I initialize with
MAX = 1e9instead ofMAX = 0to save time. This works because 1e9 is represented exactly without errors.This is a powerful technique which can be used to find floor of various function like sqrt or log. For example, to find largest long long
xsuch thatx * x <= N, I always write it as follows:This allows to compute sqrt in O(1) while I can be sure the value is correct without any floating-point shenanigans. Similarly for logs, just use
while ((1 << x) <= N) x++;how does that code finish running in the next 1000 years?
Compiler optimizations
I think he meant this part:
ll MAX = 1e9; while(MAX <= 1e18 + 1) MAX++; MAX--;
I am quite curious too, how would 1e9 operations pass for any problem with a time limit of lower than 10s?
I know, this was just some exquisite trolling ;p
version with
sqrtis legit tho, and I really use it in my code.Yes, that makes sense. I use it quite often myself :3(stole the idea from Jiangly)
Auto comment: topic has been updated by XiangXunyi (previous revision, new revision, compare).
use
1000000009and1000000000000000018, This can avoid counting the wrong number of 0.only after seeing testcase 13 where i got wrong then only i able to figure out this
how about using (1LL << 60)
You can use apostrophes in C++ integer literals, which is sometimes useful when you want to specify large constants. In this case it would be
1'000'000'000'000'000'001LL.Those who use hex numbers to define infinity.
Auto comment: topic has been updated by XiangXunyi (previous revision, new revision, compare).