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

Автор jainpavbhaji, история, 4 года назад, По-английски

I recently solved the problem of Codeforces round 146.

This is the problem statement

C++17 submission: AC submission

C++14 submission: WA submission

Both the codes are exactly same but the verdict is different.

Can anyone explain why this happens?

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

Your code C++14 submission uses LCM(int, int) and passes 2 long long arguments. Integer overflow may cause the WA verdict.

Your C++17 submission uses std::LCM(long long, long long), a template instantiation of std::LCM, which is only available since C++17. The built-in LCM function accepts two long long arguments, which does not cause integer overflow.

UPD: AC submission.

Replacing

int lcm(int a, int b){return (a*b)/__gcd(a, b);}

with

ll lcm(ll a, ll b){return (a*b)/__gcd(a, b);}

fixes the problem in C++14.

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

In C++14 your code calls on your int based lcm, which causes UB.

int lcm(int a, int b){return (a*b)/__gcd(a, b);}

Not only does it use int, it is also written in such that it can easily overflow. Switching it to

ll lcm(ll a, ll b){return a/__gcd(a, b)*b;}

gives AC 81694498.

As for why C++17 survives. In C++17 they added lcm to the standard library, so your call to lcm actually calls std::lcm.