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

Автор pfcntoorga, 13 лет назад, По-английски
I tried to submit my code with GNU C++ Compiler for 126A, then I got Wrong Answer on test #31 sadly.


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<string>
using namespace std;

const double eps=1e-8;
int main()
{
    long long t1,t2,t0,x1,x2;
    cin>>t1>>t2>>x1>>x2>>t0;
    if (t1==t2)
    {
        printf("%I64d %I64d\n",x1,x2);
        return 0;
    }
    else if (t1==t0)
    {
        printf("%I64d 0\n",x1);
        return 0;
    }
    else if (t2==t0)
    {
        printf("0 %I64d\n",x2);
        return 0;
    }
    double t=10000000;
    long long a1,a2,sum=0;
    for (long long i=0;i<=(long long)x2;i++)
    {
        long long y1=((t2-t0)*i)/(t0-t1);
        for (long long yy=min(x1,max(0ll,y1-10));yy<=max(min(x1,y1+10),0ll);yy++)
        {
            double tt1=(double)(t1*yy+t2*i)/(double)(yy+i);
            if (tt1+eps>=(double)t0 && (fabs((double)t0-tt1)<fabs(t-(double)t0) || (fabs((double)t0-tt1)==fabs(t-(double)t0) &&
                                                                  yy+i>a1+a2)))
            {
                a1=yy;a2=i;
                t=tt1;
            }
        }
    }
    printf("%I64d %I64d\n",a1,a2);
}


But, strangely, I can pass the test #31 in my own IDE with GNU C++ Compiler just modify a little bit.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<string>
using namespace std;

const double eps=1e-8;
int main()
{
    long long t1,t2,t0,x1,x2;
    cin>>t1>>t2>>x1>>x2>>t0;
    if (t1==t2)
    {
        printf("%I64d %I64d\n",x1,x2);
        return 0;
    }
    else if (t1==t0)
    {
        printf("%I64d 0\n",x1);
        return 0;
    }
    else if (t2==t0)
    {
        printf("0 %I64d\n",x2);
        return 0;
    }
    double t=10000000;
    long long a1,a2,sum=0;
    for (long long i=0;i<=(long long)x2;i++)
    {
        long long y1=((t2-t0)*i)/(t0-t1);
        for (long long yy=min(x1,max(0ll,y1-10));yy<=max(min(x1,y1+10),0ll);yy++)
        {
            double tt1=(double)(t1*yy+t2*i)/(double)(yy+i);
            if (yy==4953 && i==4533) printf("%.10f\n",tt1);
            if (tt1+eps>=(double)t0 && (fabs((double)t0-tt1)<fabs(t-(double)t0) || (fabs((double)t0-tt1)==fabs(t-(double)t0) &&
                                                                  yy+i>a1+a2)))
            {
                a1=yy;a2=i;
                t=tt1;
            }
        }
    }
    printf("%I64d %I64d\n",a1,a2);
}

Then, I tried to disabled the optimizations of speed in the compiler. Surprisingly, I can also pass the test #31 with my first version.

Knowing that the optimizations of speed is enabled in Codeforces for GNU C++, I submitted my first version with MS C++ and got Accepted finally.

Why?


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

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

Codeforces has become a great stress-test for C++ compilers, and it looks like GNU C++ definetily fails it :)

(there have been about 10 topics here about the code that is wrongly compiled by G++ with -O2 option enabled)

  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    yep... It's internal mistake about GNU C++ compiler. So strange...

  • 13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    And almost all of these topics are about stupid errors in DNA. :D
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      it's true that the optimization of compiler has some bugs...
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Make your own code bugless before blaming compiler.

        (G++ bugs are known and mostly documented - this compiler is used by millions of programmers for more than 20 platforms - so be sure it is good enough product)

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I am sorry, but I hate topics like "my program works wrong - is it a bug in GCC?" - so I allow myself a bit of sarcasm.

Your program is a sinful collection of potential bugs, but what was critical in your case - you just forgot to use "eps" which you declared when it was necessary

replace
fabs((double)t0-tt1)-fabs(t-(double)t0)

with
fabs(fabs((double)t0-tt1)-fabs(t-(double)t0))<eps

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think this problem is relevant to a question in C++ FAQ.  In short, the floating point processor may have more bits than double per register (which is the case with x86 architecture), and if GCC decides that some variable should reside in registers, some floating point operations become more precise than others.