UOJ Logo MoRanSky的博客

博客

未解之谜!代码中的超自然现象

2022-06-28 14:12:31 By MoRanSky

未解之谜!代码中的超自然现象

背景

今天上午在 vp PR2 的时候被超自然现象所击溃:花费 1h 做完的 t1,在本地对拍无误,交到 oj 上爆零了,我把错误数据在本机测试,没有任何问题,我以为是代码中存在 UB 行为,便开始调试。但是我惊奇的发现,如果我把调试信息(cout) 加上,输出答案就是正确的!在长达三个小时的奋斗后,我在代码中加入 cout<<""(输出空串),交到 oj 上,得以通过。

之后我还是百般不解,和同学花费了一个上午研究这个问题,都未得到结果,全寄了,我将详细结果写在下方,如有找到本质问题,请联系我,如若符合实情我将万分感谢。

原题及提交记录

题目:http://pjudge.ac/problem/21621 爆零代码:pjudge.ac/submission/36534 加上 cout << "" 后过了的代码:pjudge.ac/submission/36566 更换语言后通过的代码:pjudge.ac/submission/36640

简化问题

经过简化,我将出错代码浓缩成了 30 行:

// Skyqwq
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int INF = 1e9;
int n, m, k;
vector<PII> f[200][200];
PII mg (PII x, PII y) {
    return make_pair(min(x.first, y.first), max(x.second, y.second));
}
int main() {
    n = 4 , m = 2 , k = 2;
    for (int o = 0; o < 2; o++) {
         for (int i = 0; i <= n; i++) {
             f[o][i].clear();
             for (int j = 0; j <= m; j++) f[o][i].push_back(make_pair(INF,-INF));
         }
    }
    f[1][2][2] = make_pair(1, 1);
    for (int J = 2; J >= 2; J--) {
        int j = J;
        PII bella = make_pair(1000000001 , -999999999);
        PII zz = f[0][4][2];
        f[0][4][j] = make_pair(min(bella.first , zz.first) , max(bella.second , zz.second));
        // cout<<""; 
        // 加入这行以后,代码输出2:2;否则输出2:-999999998
        PII abba = make_pair(f[1][2][2].first +1 , f[1][2][2].second +1);
        if (j == 2) f[0][4][j] = make_pair(min(abba.first , f[0][4][2].first) , max(abba.second , f[0][4][2].second));
        PII nana = make_pair(f[0][4][0].first +2 , f[0][4][0].second +2);
        f[0][4][2] = mg(nana, f[0][4][j]);
    }
    cout << f[k & 1][n][m].first << " " << f[k & 1][n][m].second << endl;
    return 0;
}

程序的正确结果是 2 2,但是此代码在 uoj 系列评测机的非 c++98 的其他 c++ 版本、以及 cf 所有语言均出现错误,输出2 -999999998。在本机、锣鼓、同学电脑均未出现问题。

我们尝试了若干方式,可以得到正确结果的改善方式有如下几处(满足其一即可):

// Skyqwq
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int INF = 1e9;
int n, m, k;
vector<PII> f[200][200];
// 1. 将 vector 改成普通数组 f[200][200][200]
PII mg (PII x, PII y) {
    // 2. 在此 cout << ""; 或者 printf("");
    // 3. 添加 y = y
    return make_pair(min(x.first, y.first), max(x.second, y.second));
}
int main() {
    n = 4 , m = 2 , k = 2;
    for (int o = 0; o < 2; o++) {
         for (int i = 0; i <= n; i++) {
             f[o][i].clear();
             for (int j = 0; j <= m; j++) f[o][i].push_back(make_pair(INF,-INF));
         }
    }
    f[1][2][2] = make_pair(1, 1);
    // 4. 将 for 删掉变成 int j = 2;
    for (int J = 2; J >= 2; J--) {
        int j = J; // 8. 改为 j = 2
        PII bella = make_pair(1000000001 , -999999999);
        PII zz = f[0][4][2];
        f[0][4][j] = make_pair(min(bella.first , zz.first) , max(bella.second , zz.second));
        // 5. cout<<""; 
        PII abba = make_pair(f[1][2][2].first +1 , f[1][2][2].second +1);
        if (j == 2) f[0][4][j] = make_pair(min(abba.first , f[0][4][2].first) , max(abba.second , f[0][4][2].second));
        // 6. 把这个 if 删掉或 if (1)
        PII nana = make_pair(f[0][4][0].first +2 , f[0][4][0].second +2);
        f[0][4][2] = mg(nana, f[0][4][j]);
        // 7. 将上面的任意 j 改为 2
    }
    cout << f[k & 1][n][m].first << " " << f[k & 1][n][m].second << endl;
    return 0;
}

经过以上探索,我认为是 uoj / cf 系列编译器的底层原理和其他编译器有所不同(由 c++98 ~ c++11 中途新增的特性),应该是 vector 的内存分配出现了些许问题,但我无法解释具体出现问题的条件,也不知道问题的本质原因。

如上,这本问题的全面描述,如若还有想要了解的内容可以在评论区,我将一一回复。

评论

byqx
```cpp // Skyqwq #include <bits/stdc++.h> using namespace std; #define PII pair<int,int> const int INF = 1e9; int n, m, k; vector<PII> f[200][200]; PII mg (PII x, PII y) { return make_pair(min(x.first, y.first), max(x.second, y.second)); } int main() { n = 4 , m = 2 , k = 2; for (int o = 0; o < 2; o++) { for (int i = 0; i <= n; i++) { f[o][i].clear(); for (int j = 0; j <= m; j++) f[o][i].push_back(make_pair(INF,-INF)); } } for (int J = 2; J >= 2; J--) { int j = J; f[0][4][j] = f[0][4][2]; if (j == 2) f[0][4][j] = make_pair(2,2); PII nana = make_pair(INF,-INF); f[0][4][2] = mg(nana, f[0][4][j]); } cout << f[k & 1][n][m].first << " " << f[k & 1][n][m].second << endl; return 0; } ``` 感谢 @skip2004 再次精简bug代码
2016wudi
稍微精简了一下代码: ```cpp // Skyqwq #include <bits/stdc++.h> using namespace std; #define PII pair<int,int> const int INF = 1e9; int n, m, k; vector<PII> f; PII mg (PII x, PII y) { return make_pair(min(x.first, y.first), max(x.second, y.second)); } int main(){ f.push_back(make_pair(INF,-INF)); for (int j = 0; j >= 0; j--) { f[j] = f[0]; if (j == 0) f[j] = make_pair(2,2); f[0] = mg(make_pair(INF,-INF), f[j]); } cout << f[0].first << " " << f[0].second << endl; return 0; } ```
zero4338
再次精简版 ```cpp #include <bits/stdc++.h> using namespace std; vector<pair<int,int>>f; int mg(pair<int,int>x,pair<int,int>y) { return max(x.second,y.second); } int main() { f={{0,-11}}; for(int J=0;J<=0;J++) { f[J]=f[0]; if(J==0)f[J]={0,2}; cout<<mg({0,-8},f[J])<<endl; } return 0; } ```
zero4338
我在 cf 上问了下 https://codeforces.com/blog/entry/104300 原因好像是 O2 的 bug 原来的那份代码在我这里开 O2 也会输出 2 -999999998
Gladkowska
可能是 gcc 优化动态内存分配和指令重排时的 bug,从 gcc 5.1 开始就有了
Gladkowska
> 个人建议如果知道怎么规避就规避,编译器有很多bug,基本上报了也不会很快修复 别人给的建议
killed
@f
Gladkowska
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106131 > Comment 11 Richard Biener 2022-07-01 06:54:35 UTC > Fixed on trunk sofar. trunk 上已经修好了。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。