Same code: but C++ 17 gave a TLE, while received accepted verdict using C++ 20.

→ Обратите внимание

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
39:50:45
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 42:00:45

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Same code: but C++ 17 gave a TLE, while received accepted verdict using C++ 20.

Автор Rukashi, история, 15 месяцев назад, По-английски

Hi guys, so here's the thing:

I was so frustrated while submitting a solution to this problem : D. Reality Show, and constantly receiving a TLE verdict. I was pretty sure that the time complexity of my code was acceptable, so I decided to read the code from another. It turns out, my solution resembles their code, and after being confused for a while, I realized that they submitted it in C++ 20. After changing the language, my previous TLE code was accepted. I'm really confused right now; it's like there are some magic in C++ 20 or something.

Here is my submission:

225519286 (here's the C++ 17) 225519370 (here's the C++ 20)

Can anyone explain this to me? Thanks! :3

Rukashi
15 месяцев назад
23

Комментарии (23)

Написать комментарий?

VLTisME986

15 месяцев назад, # |

-7

haha!?

→ Ответить

i_love_turtles

15 месяцев назад, # ^ |

-9

why laughing

→ Ответить

VLTisME986

15 месяцев назад, # ^ |

-7

isnt it funny!?

→ Ответить

i_love_turtles

15 месяцев назад, # ^ |

-11

yes it is

haha!

→ Ответить

VLTisME986

15 месяцев назад, # ^ |

-12

haha!!

→ Ответить

i_love_turtles

15 месяцев назад, # ^ |

agree

→ Ответить

0x0002

15 месяцев назад, # |

← Rev. 2 →

As it says, C++20 is 64bit, but C++17 is 32bit.

Maybe this will make your code faster?

If you try using C++17(64bit) one, you can also AC.

→ Ответить

pajenegod

15 месяцев назад, # ^ |

+22

Ye, this has nothing to do with C++17 vs C++20. For example, submitting in C++17(64 bit) also results in AC 225529315.

For the future, my advice is to always submit using C++20(64 bit). The 32 bit versions are a relic of the past that shouldn't be used.

→ Ответить

AverageBasilEnjoyer

15 месяцев назад, # ^ |

Interesting, but for some reason when I was testing out my BIT template, I always get RE with C++ 20 but the same code got accepted with C++ 17, can you check why this is happening? C++ 20: https://mirror.codeforces.com/contest/61/submission/223433081 C++ 17: https://mirror.codeforces.com/contest/61/submission/223433050

→ Ответить

timreizin

15 месяцев назад, # ^ |

Your suffix_vec vector has size n, but you try to access n-th element

→ Ответить

AverageBasilEnjoyer

15 месяцев назад, # ^ |

Oh wow! then I wonder, why in C++ 17 it would pass...

→ Ответить

pajenegod

15 месяцев назад, # ^ |

+16

That's just how undefined behaviour works in C++. This is one of the big fundamental differences between coding in a language like Python compared to C++. If you try to do something unsupported in Python then it gives you an error message, but in C++ you don't know what will happen.

→ Ответить

-WIDA-

15 месяцев назад, # ^ |

← Rev. 2 →

In my personal experience, this is usually due to different operating system versions on the evaluation machines. In summary, Windows tend to be more lenient on such undefined behavior.

Below are some of my personal findings. They may not be correct, but they might give you some hints.

If you carefully read each item in the language column (especially the content in parentheses), you will notice that the 64-bit versions are all based on Windows (msys2 and winlibs). I typically use the following program for testing:

#include <bits/stdc++.h>

int main() {
    std::map<int, int> dic;
    long long x = dic.size() - 1;
    std::cout << x << "\n";
    return 0;
}

When compiled on a Windows system, you will get $$$-1$$$, which is exactly what we want. However, when compiled on Non-Windows (I can't be sure what system they are using, but it's highly likely to be Lumix), you will get a random number. You can try testing it on CodeForces Custom Test.

→ Ответить

0x0002

15 месяцев назад, # ^ |

What might be a reason is that, size() returns a number of size_t type, which is unsigned. That means, if you minus one, you won't get a correct answer.

→ Ответить

pajenegod

15 месяцев назад, # ^ |

+23

That is not undefined behaviour.

The type of .size() is size_t which is an unsigned 32 bit integer on 32 bit systems, and an unsigned 64 bit integer on 64 bit systems.

The reason the output is 4294967295 on 32 bit systems is that

unsigned int x = -1; // x becomes 4294967295 
long long y = x; // y becomes 4294967295

The reason the output is -1 on 64 bit systems is that

unsigned long long x = -1; // x becomes 18446744073709551615
long long y = x; // y becomes -1

A simple way to avoid this bug is to cast .size() to an int. That way the result will always be -1 on both 32 bit systems and 64 bit systems.

#include <bits/stdc++.h>

int main() {
    std::map<int, int> dic;
    long long x = (int) dic.size() - 1;
    std::cout << x << "\n";
    return 0;
}

→ Ответить

-WIDA-

15 месяцев назад, # ^ |

In the past, I only knew this could be used to test whether it is a 64-bit system，and now I understand the principle behind it. Thank you!

→ Ответить

tkacper

15 месяцев назад, # ^ |

← Rev. 3 →

There are some uses for 32-bit, especially if memory is the limiting factor. This code 223013153 gets RTE on C++20 (64) because of stack overflow, on other compilers it gets AC.

I was curious about that and measured the size of stack frame on each compiler:

G++20 (64) 288 B

G++17 (64) 192 B

G++17 112 B

(by measured I mean I saved the address of some local variable to a global pointer, and printed the difference of this pointer with local variable of the recursive function call — no idea if this is guaranted to be correct, but it is consistent with the fact that only G++20 RTEs)

This is just one submission, but even if G++20 (64) was as efficient as G++17 (64) this still leaves nearly 2x memory usage compared to 32-bit.

→ Ответить