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

背景

今天上午在 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 的内存分配出现了些许问题，但我无法解释具体出现问题的条件，也不知道问题的本质原因。

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

MoRanSky的博客

博客

#234 下发sample.out 有误