jainpavbhaji's blog

By jainpavbhaji, history, 5 years ago, In English

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?

  • Vote: I like it
  • -5
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.