Strange TLE by cin using GNU C++20 (64)...Again?

Revision en1, by tatianyi, 2024-05-10 09:30:16

This time, Auroraa_ is solving 524E - Ладьи и прямоугольники. After some trial, he got

this code

and then received TLE: 260160406

He was surprised, so he tried it again with exact same code, with C++17 (32). You know what? The AC magic happened again: 260161644.

At first glance, we do think some code has triggered undefined behaviours like Access out of bounds. But Auroraa_ denied that, because all the data could be fit in int32_t.

Then came the dramatic scene: by simply changing the code vector<int>v1[N], v2[N]; to vector<long long>v1[N], v2[N];, the strange TLE problem disappeared: 260164936.

After that, my further investigation[submission:260199113] pointed out that the block causes TLE is:

for (int i = 1; i <= q; i++) {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	vec.push_back({ x1, y1, x2, y2, i });
}

It took over 2000ms(260199205) to write data into this vector. And only took about 100ms(260199447) to do the same thing if we just changed vector<int>v1[N], v2[N]; to vector<long long>v1[N], v2[N];. The weirdest thing is, there is no direct connection between v1,v2 and vec.


Have you read this blog?

Tags c++, bug, compiler, 32 bit vs 64 bit, 64 bit, tle, slowdown, mingw

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English tatianyi 2024-05-17 19:16:15 225 Tiny change: Tiny difference between msvc and mingw64-gnu
en9 English tatianyi 2024-05-17 15:23:08 100 Tiny change: add Clang in the installation command.
en8 English tatianyi 2024-05-17 14:43:27 244 UPUPD change: msvc compiler also not suitable for this
en7 English tatianyi 2024-05-17 14:16:28 1209 Add a combined version that automatically finds the bomb.
en6 English tatianyi 2024-05-16 02:26:26 192 Tiny change: Headers for easy cross-platform.
en5 English tatianyi 2024-05-13 15:06:03 38 Tiny change.
en4 English tatianyi 2024-05-10 20:14:32 3365 Further investigation for MinGWs and MSYS2.
en3 English tatianyi 2024-05-10 10:38:35 164 (published)
en2 English tatianyi 2024-05-10 10:34:09 6695 Change: 'vector bomb'
en1 English tatianyi 2024-05-10 09:30:16 4047 Initial revision (saved to drafts)