yzy1's blog

A pair of parentheses make me RE
By yzy1, history, 3 years ago, In English

This morning, I spent nearly four hours to solve 455D - Serega and Fun, but I got "Runtime Error on test 9" again and again. This is one of my submissions: 132502463.

By constantly checking where the RE occurred, I located the wrong code to this line:

dq[bl[r]].erase(dq[bl[r]].begin() + r - lbl[r]);

My interpretation of it is: Delete the $$$(r-lbl_r)$$$-th element of deque dq[bl[r]]. I guess it may be because r-lbl[r] is out of bounds ($$$\notin [0,\text{size of deque})$$$) and a non-existent element is deleted, which leads to RE. But after I added two lines of assert(), I found that this is not the case.

In one attempt, I added a pair of parentheses:

dq[bl[r]].erase(dq[bl[r]].begin() + (r - lbl[r]));

But surprisingly, I got "Accepted". That's very strange. I think there is no difference between "an iterator that moves $$$x$$$ forwards and then $$$y$$$ backwards" and "moves $$$(x-y)$$$ forwards".

I want to know the difference between these two pieces of code, could someone tell me?

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

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

There is a difference. If iterator moves x forwards first it can exceed deque size.

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

    Exactly. And going out of bounds (except past-the-end iterator) is UB.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

the same as me !!!!!!!!!!

because (dq[bl[r]].begin() + r) is gonna to be out of bounds.

It will be calculated first

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

don't combine deques and iterators

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

1) Deque is not contiguous. Items not stored in one peace of memory, but in array of pointers to contiguous chunks.
2) So deque's iterator's move forward is not just "increase pointer by one" but:
a) if it is not at last item of current chunk, then increase pointer by one;
b) else find pointer of next chunk and move pointer to begin of next chunk.
3) Where to move if there is no next chunk? The hell knows. So it is UB. And backward from UB is UB too.
4) If it would be vector then it formally UB too but in practice "move x forwards and y backwards" is the same as "move (x — y) forwards"

→ Reply