Kattis平台OddGnome题C++代码本地正确提交报错排查

问题描述 #

在Kattis平台提交「OddGnome」题目的C++实现代码时被判题系统拒绝，但代码在本地运行时所有测试用例输出均符合预期，无法定位问题。

提交失败的自定义实现代码 #

#include <stdio.h>
int main(){ 
    int n, g, i;
    scanf("%d\n", &n);
    while(n--) {
        int l = -1;
        int c = 1;
        scanf("%d", &g);
        while(g--) {
            scanf("%d", &i); 
            if (l == -1) l = i;
            else if (i - 1 != l) break;
            else l++;
            c++;
        }
        fflush(stdin);
        printf("%d\n", c);
    }
} 

可正常通过判题的参考实现 #

从公开渠道找到的同题代码可以正常通过Kattis判题，本地测试时其输出结果与上述自定义实现完全一致，代码如下：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    //Initialize n and g, take in n
    int n, g;
    cin >> n;

    //Iterate n times
    while (n--)
    {
        //Take in g, initialize empty vector of size g
        cin >> g;
        vector<int> gnomes(g);

        //Take in all the gnomes
        for (int i = 0; i < g; i++) cin >> gnomes[i];

        //Iterate through without the beginning or end since king won't be there
        for (int i = 1; i < g-1; i++)
        {
            //Must break the order, and if you remove it the gnomes around it should be in order
            if (gnomes[i] < gnomes[i-1] || gnomes[i] > gnomes[i+1] && gnomes[i-1] < gnomes[i+1])
            {
                //Output the 1 based index, so add 1
                cout << i+1 << endl;

                //And exit to the next group
                break;
            }
        }
    }
}

代码问题与判题失败原因 #

你的代码存在两个核心问题，本地运行正常完全是特定环境下的巧合：

• 未定义行为调用：fflush(stdin)
  C/C++标准中仅定义了fflush对输出流的操作行为，对输入流（比如stdin）调用fflush属于标准明确标注的未定义行为，不同操作系统、编译器下的表现没有任何保证。本地运行环境大概率是Windows系统，部分编译链（比如旧版MSVC）额外实现了fflush(stdin)清空输入缓冲区的逻辑，所以本地运行不会出问题；但Kattis判题机运行在Linux环境，glibc库对fflush(stdin)不会执行清空输入的操作，甚至可能触发流状态异常，直接导致输入输出逻辑混乱。
• 输入读取不完整导致的解析错位
  代码在找到顺序断裂的侏儒位置后会直接break跳出当前组的输入循环，没有消费完当前组剩余的输入数据。如果去掉fflush(stdin)，这些残留在输入缓冲区的数据会被下一轮循环的scanf误读，直接导致后续所有测试组的输入解析完全错位，输出错误结果。本地能得到正确输出，完全是依赖Windows环境下fflush(stdin)偶然清空了残留输入，不属于逻辑层面的正确。

对比参考实现可以看到，可通过的代码会先完整读取当前组所有g个输入数据存入数组，再遍历查找异常位置，不存在残留输入的问题，也没有任何未定义行为的调用，在任何符合标准的编译环境下都能稳定运行。

修复方案 #

可选择任意一种方式修改代码：

• 去掉fflush(stdin)调用，找到异常位置后不要直接跳出输入循环，继续读完当前组剩余的所有输入，再输出结果；
• 参考公开实现的逻辑，先完整读取当前组所有输入，再做异常位置计算。

内容的提问来源于stack exchange，提问作者Matthew Tello