adamant's blog

By adamant, history, 7 weeks ago, In English,

Okay, so compare these two submissions: 51053654 and 51053605

The only difference is that first one made via GNU C++17 and the second one via MS C++ 2017. Code is same, but first gets RE 16 and second one gets AC.

WTF, GNU C++??

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

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

UB maybe?

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

    Can you see any? For me code seems pretty clear. I'd rather expect that somehow they optimize code differently which leads first one in stack limit. It's not very realistic though because I had a GCC version running into TL 18 (thus passing 16th test): 51022745

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

If depth of your dfs may be >= 1e6, then it's stack overflow. And in that case "WTF" can be easy explained by different stack size or/and different bytes-on-stack-per-recursive-call used by the compiler.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it really stack overflow? Stack on codeforces is 256 mb: Link

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

      Note that test 16 is one of the test where memory consumption is maxed for your MSVC solution and it's >400mb with GCC. So maybe you actually use more than 256mb of stack in that case?

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      What is actual max depth of recursion? If I interpret these submissions correctly: 51057215 51057182, 1 level of recursion eats 28 bytes on msvc and 64 bytes on GCC

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

        So, If I interpreted it correctly, the depth is 5e6 and so with msvc you use ~150mb+28*5e6=~290mb. with gcc you use 320mb of stack

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +19 Vote: I do not like it

      So, as we discussed with adamant elsewhere, the problem was indeed in the stack size.

      AC submission: 51059986

      So the problem can be avoided by creating new stack with increased max stack size. You can copypaste snippet at the end of the code to your template to forget about the stack size

      --

      One open question is why gcc require two times more memory

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

same thing((( 51079321 51026165.

Didn't think about stack size

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, please compare these two submissions: 51586126 and 51586141. The only difference is that the first one adding the inline specifier onto the tarjan function and gets AC, the second one without inline gets RE 16.

Any ideas?