EugeneJudo's blog

By EugeneJudo, history, 3 years ago, In English

I've been compiling locally with c++11, e.g. g++ -Wall -Wextra -Wpedantic -std=c++11 -o "D" "D.cpp", and I've been trying to figure out why I'm getting different results remotely. I submitted the same code to:

GNU C++11 (fails) https://codeforces.com/contest/1493/submission/110434447

GNU C++14 (passes) https://codeforces.com/contest/1493/submission/110479676

Locally my c++11 compilation is not getting the error shown in the submission on problem set 3. My gut feeling is that there's some out of bounds write occurring that i'm missing that just isn't affecting things by luck in the other submission, but if it is I just can't detect it. I would appreciate any insight (or critique of my code.)

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
3 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Not sure if this helps, but pow() is inconsistent; see below

int main() {
	const long long x = 2039593823;
	cout << (long long)pow(x,2) << "\n";
	cout << x*x << "\n";
	// 4159942962819755520
	// 4159942962819755329
}
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yeah it is the pow function. When you use pow, you are dealing with floating points which are not accurate. You should write a function which doesn't involve floating points.

    Something like this

    Here is the link to the accepted submission.

    sqrt involves floating points as well. It's better to do f*f <= tmp

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

    Thank you! I'm a little surprised actually that the standard library pow doesn't have an overloaded case for just ints and long long ints to return a long long int, but it's great to know.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think the main reason the standard library doesn't have an overloaded case for ints or long longs is because it is easy to have overflow in those cases, but floating point multiplications are easy to scale to large powers.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Yeah, but some kind of modpow() function would be nice, because it's used quite a bit, even outside of cp I think. iirc, Python has an optional mod in its pow() function.