evilbuggy's blog

Why codeforces gives different output?
By evilbuggy, history, 6 years ago, In English 
#include <bits/stdc++.h>

using namespace std;

bool overflow(long long int a, long long int b){
    long long int c = a*b;
    cout<<a<<" "<<b<<" "<<c<<" "<<c/a<<" "<<c/b<<endl;
    return (c/b) != a;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long int a = 847288609443LL; // 3^25
    cout<<overflow(a, a)<<endl;
}

When I run the above code in my PC I get the following output...

847288609443 847288609443 6048575297968530377 7138742 7138742
1

But when I run it on codeforces I get the following output....

847288609443 847288609443 6048575297968530377 7138742 847288609443
0

What could be the problem here? Btw Why c/a and c/b different in codeforces output though a and b have same value?

Please help me out.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Overflowing signed integers is undefined behaviour. In that case, anything may happen in your program. Moreover the compiler may assume that the overflow does not occur and use this for optimization. There's a nice example on ideone. (You can run it in custom invocation too, but it takes a long time as it prints a ton of numbers.)

In your case, I guess that you locally compiled without optimizations (no -O2), while codeforces uses -O2. The compiler may assume that c = a*b does not overflow, so it can optimize c/b to a. I don't know why c/a does not get optimized. (Clang optimizes both divisions away, you can check it on godbolt).

If you want to check for overflow, use __builtin_smulll_overflow or some other bultin function from here.

→ Reply