Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 7:00 (UTC) due to technical maintenance. ×

Strange TLE by cin using GNU C++20 (64), and some weird subtle changes to (surprisingly) fix it

Revision en11, by -14, 2024-03-01 11:28:51

When I was doing the problem C. Pokémon Arena in the last Div. 1 round, I submitted my solution and got a TLE on pretest 20.

I was not suspecting anything but my code, I thought there may be some degenerate issue, undefined behavior or constant issue, but nothing really found. After some unsuccessful attempts, I was able to pass the pretest using fast IO. It's then I found something weird: it only takes a few hundred milliseconds, which is contradictory to my intuition: cin with sync_with_stdio(false) is fairly fast and it should not take up so much more (at least 10x) time.

After the contest, I submitted exactly the same code with different language. You know what?

It's not only me, and some other participants also encountered such issue. For example:

Here's snippet for the key code:

int n, m;
cin >> n >> m;
vector a(n, vector (m, 0));
vector c(n, 0);
for (int i = 0; i < n; i++) cin >> c[i];
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		cin >> a[i][j];
	}
}

But there are also some successful cin submissions using GNU C++20 (64). After investigation by (including but not limited to) Sugar_fan, Boboge, -skyline-, the key components of TLE are:

  • The language must be GNU C++20 (64).
  • vector must be of int. If the elements are long long, it passed. 249050206
  • The definition of 2D vector must be before reading c. If swap these two lines, it passed. 249050425

So here's the thing. It could not even be simply interpreted as some branch mispredictions or cache misses, it seems something is completely broken, and we still don't understand what is actually wrong.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English -14 2024-03-01 11:28:51 10
en10 English -14 2024-03-01 10:50:50 11
en9 English -14 2024-03-01 02:16:56 1 Tiny change: '248983571]\n\nIt's n' -> '248983571].\n\nIt's n'
en8 English -14 2024-03-01 02:15:47 2 Tiny change: ' not limit to) [user' -> ' not limited to) [user'
en7 English -14 2024-03-01 02:15:26 148
en6 English -14 2024-03-01 02:15:00 8
en5 English -14 2024-03-01 02:12:23 22 (published)
en4 English -14 2024-03-01 02:11:45 2 Tiny change: 'ion of 2D vector must be b' -> 'ion of 2D `vector` must be b'
en3 English -14 2024-03-01 02:11:02 125
en2 English -14 2024-03-01 02:08:21 78
en1 English -14 2024-03-01 02:06:15 2059 Initial revision (saved to drafts)