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

Автор radoslav11, история, 9 лет назад, По-английски

While solving Goodbye 2015, E i was getting TL on test 11. Now after the contest I decided to see what was the problem.

After some debugging I found that when you do lower bound on an empty set it gives TL:

http://mirror.codeforces.com/contest/611/submission/15127498 — AC
http://mirror.codeforces.com/contest/611/submission/15126396 — TL11

The only difference is if(s.size() == 0) break;

So I want to ask if there are similar issues with the std::set.

PS: This was a good lesson for me. Next time I wont try debugging one solution for 2 hours and will solve the other problems.

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

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится -12 Проголосовать: не нравится

.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    It actually will never be infinite. I've even added another way of breaking it: if the size of the set last time (last_sz) is equal to the current size, then I just break the cycle. I also debugged it and while doing so it turned out that after s.lower_bound({c[0], 0}) it the program didn't continue and just made this operation for infinite time.

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

If s is empty you try to erase s.end(). As I understand it's undefined behaviour.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    You're right. . .
    I feel so dumb now. But still I'll know this for next time. :/

    Thanks!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    But then should't it crash?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Undefined behaviour means anything could happen. Anything. It could even print "I love pancakes" and then crash, and it would be still ok according to the documentation. But yes, crashing is what you would expect the most.