never_giveup's blog

By never_giveup, history, 6 years ago, In English

Hello, I was solving golf from JOI 2017 Open. I tested in polygon with author's solution. My solution got WA, then I decided to change C++17 to C++14 and magically I've got AC. Can someone tell me how is that possible. Also I submitted it to oj.uz where compiler is under Ubuntu and it also gives wrong answer code test

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

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

I changed links to array, still doesn't work. code

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

Undefined behaviour or bug in g++. It's so obvious.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    So why UD should work in other compilers than C++17

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

      It's not really that it "works" in C++14, it just happened to not fail. You know, because it's undefined behavior.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -13 Vote: I do not like it

        Not to fail in 50 tests? Seems quite strange to me.

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

          You are yellow, was red, and act like a green. You are able to handle this thing by yourself.

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

            If I was able to, I wouldn't ask to help me. This is too hard for "yellow".

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

              Line 255-256:

              set<int> :: iterator it = st.upper_bound(its.sc.fr);
              it--;
              

              Sometimes upper_bound returns st.begin() causing undefined behavior when you decrement the iterator. Did you even try to test for UB before you made a codeforces blog to cry about C++17?

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

                Why are you so mad, not everyone so smart like you. I never heard that upper_bound can return begin. Also I inserted -1 and inf some lines above and I can't remove them.

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

                  Yes you did. You inserted -1 above.And then you proceeded to check for -inf. Inserting -1 literally does nothing. If you insert -inf then it outputs the correct answer.

                  "I never heard that upper_bound can return begin". I actually wonder how you were once red...

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

                  Values that I use for upper and lower bound are in range 0..2*n+2, I use -inf for removing elements and inf to inserting elements as you can see.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Oh, actually I understood what you meant with upper_bound returning begin, I thought if there is no element instead of end it returns begin. Haha :D Anyway it can't happen, you can set assert if you don't believe.

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

Is 10 the correct answer to test?

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

If someone was wondering what was the problem. I found bug, actually in Windows C++14 and earlier when you access element of map, it creates if wasn't firstly. I was using it to compress values on lines 216-217. So in Windows elements started from 0, and in Linux from -1.