这是一个完全符合你要求的数据生成器。

这份代码集成了标准解法（这里为了保证绝对正确性，生成器内部使用 std::sort 生成标准输出，因为它是 C++ STL 经过验证的排序算法，作为“真理”最合适）和10种精心设计的测试点生成策略。

它会生成 1.in/1.out 到 10.in/10.out，覆盖了题目 $N \le 300$ 的范围下的各类情况，包括单色、缺色、逆序、随机等场景。

C++ 数据生成器代码

请保存为 generator.cpp，编译并运行。

/**
 * 题目：颜色分类 (Sort Colors) - 数据生成器
 * 功能：生成 1.in/1.out ~ 10.in/10.out
 * 环境：C++14 Standard
 * 作者：OI Gold Medal Coach
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
#include <string>

using namespace std;

// ==========================================
// Part 1: 标准解法 (Solver)
// ==========================================
// 用于生成 .out 标准答案
// 在生成器中，我们为了保证输出数据的绝对正确性，通常直接使用 STL sort。
// 题目要求选手手写排序，但判题机需要的标准答案只需要排序结果正确即可。
class Solver {
public:
    vector<int> solve(vector<int> nums) {
        // 直接使用 std::sort 保证 ground truth 的正确性
        sort(nums.begin(), nums.end());
        return nums;
    }
};

// ==========================================
// Part 2: 数据生成工具箱
// ==========================================
mt19937 rng(time(0));

// 生成指定长度、指定颜色分布权重的随机数组
// weights: {w0, w1, w2} 分别代表 0, 1, 2 出现的相对概率
vector<int> gen_weighted_random(int n, vector<int> weights) {
    vector<int> res;
    res.reserve(n);
    
    // 构建分布池
    vector<int> pool;
    for (int c = 0; c <= 2; ++c) {
        for (int k = 0; k < weights[c]; ++k) {
            pool.push_back(c);
        }
    }
    
    if (pool.empty()) pool.push_back(0); // 防御性

    uniform_int_distribution<int> dist(0, pool.size() - 1);
    for (int i = 0; i < n; ++i) {
        res.push_back(pool[dist(rng)]);
    }
    return res;
}

// 生成特定模式：逆序 (2 -> 1 -> 0)
vector<int> gen_reverse_sorted(int n) {
    vector<int> res;
    int c2 = n / 3;
    int c1 = n / 3;
    int c0 = n - c2 - c1;
    
    for(int i=0; i<c2; ++i) res.push_back(2);
    for(int i=0; i<c1; ++i) res.push_back(1);
    for(int i=0; i<c0; ++i) res.push_back(0);
    return res;
}

// 生成特定模式：交替 (0, 1, 2, 0, 1, 2...)
vector<int> gen_alternating(int n) {
    vector<int> res;
    for(int i=0; i<n; ++i) res.push_back(i % 3);
    return res;
}

// ==========================================
// Part 3: 主程序
// ==========================================
int main() {
    Solver solver;
    cout << "Generating test data for Sort Colors..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_file_name = to_string(i) + ".in";
        string out_file_name = to_string(i) + ".out";
        
        ofstream fin(in_file_name);
        ofstream fout(out_file_name);
        
        int N;
        vector<int> input_nums;
        string desc;

        // ---- 针对不同测试点设计数据 ----
        switch(i) {
            case 1: 
                // 边界：极小值 N=1
                N = 1;
                input_nums = {2}; 
                desc = "Min N=1";
                break;
            case 2: 
                // 边界：极小值 N=2 (无序)
                N = 2;
                input_nums = {2, 0}; 
                desc = "Min N=2 Unsorted";
                break;
            case 3: 
                // 特殊：全 0 (单色)
                N = 10;
                input_nums = gen_weighted_random(N, {1, 0, 0}); 
                desc = "All 0s";
                break;
            case 4: 
                // 特殊：全 2 (单色)
                N = 10;
                input_nums = gen_weighted_random(N, {0, 0, 1}); 
                desc = "All 2s";
                break;
            case 5: 
                // 特殊：缺失 1 (只有 0 和 2)
                // 考察算法是否依赖中间值 1 的存在
                N = 20;
                input_nums = gen_weighted_random(N, {1, 0, 1}); 
                desc = "Missing 1 (Only 0, 2)";
                break;
            case 6: 
                // 特殊：逆序 (最坏情况之一)
                N = 50;
                input_nums = gen_reverse_sorted(N); 
                desc = "Reverse Sorted (2..1..0)";
                break;
            case 7: 
                // 正常随机：均匀分布
                N = 100;
                input_nums = gen_weighted_random(N, {1, 1, 1}); 
                desc = "Random Uniform";
                break;
            case 8: 
                // 正常随机：偏斜分布 (大部分是 1)
                // 考察大量中间元素时的指针移动效率
                N = 200;
                input_nums = gen_weighted_random(N, {1, 8, 1}); 
                desc = "Random Skewed (Mostly 1s)";
                break;
            case 9: 
                // 特殊：交替出现
                // 考察频繁交换
                N = 300;
                input_nums = gen_alternating(N); 
                desc = "Alternating (0,1,2,0,1,2...)";
                break;
            case 10:
                // 大数据：N=300 (题目上限)
                // 完全随机，模拟最终测试
                N = 300;
                input_nums = gen_weighted_random(N, {1, 1, 1}); 
                desc = "Max N Random";
                break;
        }

        // ---- 写入 .in 文件 ----
        // 格式：
        // N
        // num1 num2 ... numN
        fin << N << endl;
        for (int k = 0; k < N; ++k) {
            fin << input_nums[k] << (k == N - 1 ? "" : " ");
        }
        fin << endl; // 保持文件末尾换行习惯

        // ---- 计算并写入 .out 文件 ----
        vector<int> result = solver.solve(input_nums);
        
        // 格式：
        // res1 res2 ... resN
        for (int k = 0; k < N; ++k) {
            fout << result[k] << (k == N - 1 ? "" : " ");
        }
        fout << endl;

        // ---- 关闭文件 ----
        fin.close();
        fout.close();

        cout << "Generated Case " << i << ": " << desc << " [N=" << N << "]" << endl;
    }

    cout << "\nAll 10 test cases generated successfully!" << endl;
    return 0;
}

判题与数据说明

1. 输入格式：

   • 第一行：整数 $N$。
   • 第二行：$N$ 个空格分隔的整数（0, 1, 或 2）。
   • 注：这完全符合之前我给出的题目描述格式。

2. 输出格式：

   • 一行：$N$ 个空格分隔的整数，表示排序后的结果。

3. 测试点覆盖策略：

   • Test 1-2: 覆盖极小值 $N=1, 2$，防止下标越界或空指针错误。
   • Test 3-4: 覆盖单色情况（全0或全2），这是三指针算法容易出错的地方（比如指针一直移动导致越界）。
   • Test 5: 覆盖缺色情况（只有0和2，没有1），考察算法是否硬性依赖中间区域。
   • Test 6: 逆序数组，对于某些依赖特定顺序的错误贪心算法是杀手。
   • Test 7, 10: 随机均匀分布，常规测试。
   • Test 8: 大量 1，考察算法对中间区域的处理效率（如果 curr 移动逻辑有误，可能变慢或出错）。
   • Test 9: 交替分布，考察频繁交换下的稳定性。

4. 使用方法：

   • 直接编译运行 g++ generator.cpp -o gen && ./gen。
   • 生成的 .in 和 .out 文件可以直接导入 OJ 系统（如 Hydro, HUSTOJ, QDUOJ 等）。
   • 判题模式选择文本对比 (Diff / Standard) 即可（忽略行末空格和换行）。

你好！我是你的OI竞赛金牌教练。

针对《颜色分类》（荷兰国旗问题），这是考察多指针协作（Multi-pointers）与不变量维护的经典题目。

在 NOIP/CSP 考场上，虽然使用计数排序（两遍扫描）也能拿满分，但如果能写出一遍扫描的“三指针法”，会让阅卷老师（或者面试官）眼前一亮，因为这展示了更强的思维控制力。

下面是完全符合 NOIP C++14 竞赛标准 的标准代码。

NOIP 标准题解代码 (C++14)

/**
 * 题目：颜色分类 (Dutch National Flag Problem)
 * 算法：三指针法 (Three Pointers) / 单次扫描原地排序
 * 时间复杂度：O(N)
 * 空间复杂度：O(1)
 * 风格：NOIP/CSP 竞赛标准
 */

#include <iostream>
#include <vector>
#include <algorithm> // for std::swap

using namespace std;

// 开启 IO 优化，适应大规模数据输入
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    fast_io();

    // 1. 读入数据
    int n;
    if (!(cin >> n)) return 0; // 鲁棒性检查

    // 使用 vector 存储
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // 2. 算法核心：三指针法 (荷兰国旗划分)
    // p0: 左边界指针，保证 [0, p0) 范围内的元素全为 0 (红色)
    // p2: 右边界指针，保证 (p2, n-1] 范围内的元素全为 2 (蓝色)
    // curr: 当前遍历指针，[p0, curr) 范围内的元素全为 1 (白色)
    
    int p0 = 0;
    int curr = 0;
    int p2 = n - 1;

    // 【易错点1】 循环结束条件必须是 curr <= p2
    // 因为 p2 指向的位置可能是待处理的未知元素（或者是刚交换过来的 0/1/2），
    // 必须让 curr 扫描到 p2 这个位置，才能保证没有漏网之鱼。
    while (curr <= p2) {
        if (nums[curr] == 0) {
            // Case 1: 遇到 0 (红色)
            // 把它放到左边 0 的区域去，也就是和 p0 位置交换
            // 因为 p0 和 curr 之间全是 1，所以换过来的肯定是 1 (或者 curr==p0)，
            // 1 不需要再次检查，所以 curr 可以放心右移
            swap(nums[curr], nums[p0]);
            p0++;
            curr++;
        } 
        else if (nums[curr] == 2) {
            // Case 2: 遇到 2 (蓝色)
            // 把它放到右边 2 的区域去，也就是和 p2 位置交换
            // 【易错点2】 交换后，curr 不能移动！
            // 因为从 p2 换回来的那个数是从后面来的“未知数”，可能是 0，也可能是 2，
            // 必须在下一次循环中重新检查 nums[curr]。
            swap(nums[curr], nums[p2]);
            p2--;
            // 注意：这里 curr 不 ++
        } 
        else {
            // Case 3: 遇到 1 (白色)
            // 1 本来就在中间，属于合法位置，直接跳过
            curr++;
        }
    }

    // 3. 输出结果
    for (int i = 0; i < n; ++i) {
        cout << nums[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

复杂度分析与思考过程

1. 时间复杂度分析

• 思考过程：
  • 我们需要考察算法中的 curr 指针移动次数。
  • 在每次 while 循环中，curr 要么向右移动（遇到 0 或 1 时），要么 p2 向左移动（遇到 2 时）。
  • curr 和 p2 的总距离是 $N$，每次循环两者之间的距离缩短 1。
  • 因此，总的操作次数严格受限于 $N$。
• 结论：时间复杂度为 $O(N)$。这是一次遍历（One-pass）算法。
• 优化建议：对于这道题，$O(N)$ 已经是理论下界（必须看一遍所有元素）。这已经是最高效的解法。

2. 空间复杂度分析

• 思考过程：
  • 题目要求 原地 (In-place) 排序。
  • 我们只使用了 p0, curr, p2, n, i 这几个整型变量，以及 swap 操作需要的临时变量。
  • 没有申请与 $N$ 相关的额外数组（如计数数组或临时 buffer）。
• 结论：空间复杂度为 $O(1)$。

教练的草稿纸图解 (Trace)

假设输入：[2, 0, 2, 1, 1, 0]，n = 6。

初始状态： p0 = 0, curr = 0, p2 = 5

1. Iter 1: nums[curr] (2) 是 2。

   • Swap nums[0] 和 nums[5] (0)。数组变为 [0, 0, 2, 1, 1, 2]。
   • p2 变为 4。
   • curr 不动 (还是 0)。
   • 注意：此时 nums[0] 变成了 0，还没检查过。

2. Iter 2: nums[curr] (0) 是 0。

   • Swap nums[0] 和 nums[p0] (也就是自己换自己)。
   • p0 变为 1。
   • curr 变为 1。

3. Iter 3: nums[curr] (0) 是 0。

   • Swap nums[1] 和 nums[p0] (也是自己换自己)。
   • p0 变为 2。
   • curr 变为 2。
   • 数组现状：[0, 0, 2, 1, 1, 2]，p0 指向第3个元素。

4. Iter 4: nums[curr] (2) 是 2。

   • Swap nums[2] 和 nums[p2] (nums[4]=1)。数组变为 [0, 0, 1, 1, 2, 2]。
   • p2 变为 3。
   • curr 不动 (还是 2)。

5. Iter 5: nums[curr] (1) 是 1。

   • curr 变为 3。

6. Iter 6: curr (3) <= p2 (3)，继续。

   • nums[3] 是 1。
   • curr 变为 4。

7. 结束：curr (4) > p2 (3)，循环结束。

最终结果：0 0 1 1 2 2。完美排序。

总结关键点

1. “未知区域”的压缩：把三指针看作是三个挡板，[0, p0) 是红色，[p0, curr) 是白色，(p2, n-1] 是蓝色。[curr, p2] 是中间未探索的区域。循环的目的就是把这个未探索区域缩减为 0。
2. Swap 后的回头看：遇到 2 交换后，千万不要移动 curr，这是本题唯一的坑。因为你从后面换上来的可能是个 0，如果 curr 走了，这个 0 就被当成 1 永远留在中间了。