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

Автор era404, история, 18 месяцев назад, По-английски
  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
18 месяцев назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

You should notice that you changed the language of the submission: C++17 versus C++17 (64). The first one uses 32-bit architecture while the second one uses 64-bit architecture. This is what is happening:

Let's look at the following line:

for(ll i=v.size()-2;i>=0;--i){

The problem occurs you try to calculate v.size()-2. In the third test case, $$$n = 1$$$ and it has only one digit. The size of the vector will be equal to 1. Now, v.size() equals 1. Thus, v.size()-2 equals -1, right? Actually, no. v.size() and other container sizes are always stored in an unsigned integer type. On a 32-bit architecture this is a 32-bit unsigned integer (i.e. the same as unsigned int). When subtraction goes below zero on unsigned integers, integer overflow happens. In this case, the value of v.size()-2 will be equal to $$$2^{32}-1$$$ or 4294967295. Since this value is put into a signed 64-bit variable, there are enough bits to store the value and the loop will start at i = 4294967295 indexing the array out of bounds and giving you RTE.

In the second submission, the same problem occurs. This time v.size() is a 64-bit unsigned integer. Overflow happens with the subtraction and now, v.size()-2 will be equal to $$$2^{64}-1$$$ or 18446744073709551615. This will now be stored in a signed 64-bit variable. But the signed 64-bit variable does not have enough space to store this big positive integer. It will be converted to the negative equivalent value, which is exactly $$$2^{64}$$$ less than that positive value. Thus, the negative value will be the original $$$-1$$$ and the code will run succesfully.

The best way to avoid this mistake is to always typecast container sizes to int or long long like this:

for(ll i=(int)v.size()-2;i>=0;--i){

or

for(ll i=(ll)v.size()-2;i>=0;--i){

This will ensure that the subtraction is done on signed integers and will not overflow.