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:
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.
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 :')