Hi!

Yesterday I was solving problem 1743C - Save the Magazines, when I faced a strange verdict. My code was getting WA with C++20 (176908643), while everything was ok with C++17 (176909474, 176989803). I tried looking for anything in my code that may cause undefined behavior, nothing found. Also there were something more strange as well; Like these two:

• Changing the order of two variables in line 43 caused different verdict (176965105).

• Adding a single line of cerr << 1;, again,caused different verdict (176965552).

and many other strange behaviours...

Here's a smaller code which has different verdicts in GNU G++20 11.2.0 (64 bit, winlibs) and GNU G++17 7.3.0 on Codeforces's custom test. You can check it out yourself, but as far as I know there's nothing special or causing undefined behaviour in this code:

#include<bits/stdc++.h>

/*
Woman
Life
Freedom
*/

using namespace std;
 
typedef int ll;
 
const int maxn5 =  100;
 
ll a[maxn5] = {10, 5, 8, 9, 6};
ll dp[2][maxn5];

ll my_max(ll x, ll y)
{
	return x>y? x+1: y+1;
}
 
int main()
{
        int n = 5;
        string s = "01110";
        cin >> a[n];
        for(int i = 1; i < n; i++){
            dp[1][i] = 0;
	    dp[0][i] = 0;
            dp[0][i] = my_max(dp[1][i - 1], dp[0][i - 1]);
            if(s[1] != '0')
                dp[1][i] = 100;
        }
        cout << dp[0][n - 1] << '\n';
}

UPD: Simpler code by pajenegod

UPD 2: Extremely simpler code by nor

UPD 3: I also reported the problem on Bugzilla (Link)

What's really happening ?

It's all about tree-loop-distribute-patterns flag. You can learn about it here. But there's a problem in GCC 11.2. While compiling a code like:

for (...) {
    a[i] = 0;
    b[i] = 0;
    if (...) a[i] = a[i-1] + 1;
}

it generates something like:

memset(a, 0, sizeof a);
for (...) {
    if (...) a[i] = a[i-1] + 1;
}
memset(b, 0, sizeof b);

And that's why the verdict differs just by changing the order of those two variables. As you can see here:

• First there's a memset in line 85.

• Then the for will run.

• Finally in line 122 there's the last memset, which destroys everything!

It seems that this problem starts from GCC 10.1, so GNU G++17 7.3.0 and GNU G++17 9.2.0 work correctly.

The default optimizition used by Codeforces for both C++20 and C++17 is O2. The flag tree-loop-distribute-patterns works automatically in O2 and later. So the code with O1 optimization will run correctly. In O3 and later, another flag, tree-vectorize, has been included, which fixes this bug; So, again, if you use O3 or Ofast it will run correctly.

• tree-vectorize -> AC 177021996
• O1 -> AC 176935274
• O2 -> WA 176934914
• O3 -> AC 176935180
• Ofast -> AC 176935136
• O2 + tree-vectorize -> AC 176984080
• O2 + no-tree-loop-distribute-patterns -> AC 176984219
• O1 + tree-loop-distribute-patterns -> WA 176984329
• O3 + no-tree-vectorize -> WA 176998110
• Ofast + no-tree-vectorize -> WA 176998186

But there's still something strange. The code with O0 works ok (177008931), also the one with an extra flag tree-loop-distribute-patterns wroks ok as well! (177008871)

Anyway! It's a serious bug, but it seems that ‍O2 in GCC 12 has the flag tree-vectorize. So currently, with this version of GCC which is the only available version for C++20 here, it isn't safe to use C++20 on Codeforces without extra flags (at least for me!). I highly recommend using C++17 instead of C++20 if possible, or using some extra flags like tree-vectorize, I truly hope this one won't cause any other strange behaviour!

Thanks to Davoth, ymmparsa and specially AaParsa that almost everything I shared was with great help of them. I was just the poor one who faced the problem :')